domino_lib/generate/
mod.rs

1//! This module provides functionality for generating valid puzzle instances.
2//!
3//! It includes a function to generate a puzzle with a valid Eulerian cycle and remove a specified number of tiles.
4
5use std::time::{Duration, Instant};
6
7use crate::{classify_puzzle, utils::find_eulerian_cycle, validate_puzzle, ComplexityClass, Graph, Puzzle, Solution, Tile};
8use rand::Rng;
9
10/// Generates a puzzle with a valid Eulerian cycle and removes a specified number of tiles.
11///
12/// This function constructs a `Graph` representation of the puzzle, finds an Eulerian cycle,
13/// and converts the cycle into a `Solution`. Then, it removes a specified number of tiles
14/// either sequentially or randomly, based on the `random` flag.
15///
16/// # Arguments
17///
18/// * `n` - The size of the puzzle.
19/// * `minimum_removals` - The number of tiles to remove from the solution.
20/// * `random` - If `true`, removes tiles at random; otherwise, removes them sequentially.
21///
22/// # Returns
23///
24/// A `Puzzle` instance with `Some(Tile)` values for placed tiles and `None` for removed tiles.
25pub fn generate_puzzle(n: usize, c: usize) -> Puzzle {
26    let graph = Graph::regular(n);
27    let eulerian_cycle = find_eulerian_cycle(&graph,true);
28    let mut solution: Solution = create_solution_from_cycle(&eulerian_cycle);
29    let mut puzzle= solution.clone().into_iter().map(Some).collect::<Vec<Option<Tile>>>();
30    let mut rng = rand::thread_rng();
31
32    // Complexity checks
33    let mut expected_complexity = ComplexityClass::new(c).ok();
34    let mut actual_complexity: Option<ComplexityClass> = None;
35    let mut is_not_complex_enough = actual_complexity != expected_complexity;
36    let mut is_too_complex = false;
37
38    // Timeout
39    let mut now = Instant::now();
40    let timeout = Duration::from_millis(2000);
41
42    // Validity checks
43    let is_not_valid = validate_puzzle(&puzzle.clone().into(), &solution).is_err();
44
45    // Removal history
46    let mut index = rng.gen_range(0..puzzle.len());
47    let mut removal_history: Vec<(Option<Tile>, usize)> = vec![(puzzle[index].clone(), index)];
48    puzzle[index] = None;
49
50
51    // Remove tiles
52    while is_not_valid || is_not_complex_enough {
53
54      while is_too_complex {
55        // println!("is_too_complex");
56        reinsert_tile(&mut puzzle, &mut removal_history);
57        update_complexity(&mut actual_complexity, &mut expected_complexity, &puzzle, &mut is_not_complex_enough, &mut is_too_complex);
58      }
59
60      let removed_tile: Option<Tile>;
61      let removed_position: Option<usize>;
62
63      // Remove a tile at a true position
64      (puzzle, removed_tile, removed_position) = remove_non_empty_tile(puzzle);
65      removal_history.push((removed_tile, removed_position.unwrap()));
66
67      // Update complexity checks
68      update_complexity(&mut actual_complexity, &mut expected_complexity, &puzzle, &mut is_not_complex_enough, &mut is_too_complex);
69
70      // Update validity checks
71      let is_not_valid = validate_puzzle(&puzzle.clone().into(), &solution).is_err();
72
73      // The puzzle becomes invalid rollback
74      if is_not_valid {
75        reinsert_tile(&mut puzzle, &mut removal_history);
76        update_complexity(&mut actual_complexity, &mut expected_complexity, &puzzle, &mut is_not_complex_enough, &mut is_too_complex);
77      }
78
79      // If the time spent trying to reach the desired complexity is greater than the timeout then restart with another initial solution
80      if now.elapsed().as_millis() > timeout.as_millis() || actual_complexity.is_none(){
81        // println!("timeout, puzzle is: {puzzle:?}");
82        solution = create_solution_from_cycle(&eulerian_cycle);
83        puzzle = solution.clone().into_iter().map(Some).collect::<Vec<Option<Tile>>>().into();
84        index = rng.gen_range(0..puzzle.len());
85        removal_history = vec![(puzzle[index].clone(), index)];
86        puzzle[index] = None;
87        update_complexity(&mut actual_complexity, &mut expected_complexity, &puzzle, &mut is_not_complex_enough, &mut is_too_complex);
88        now = Instant::now();
89      }
90
91    }
92
93    puzzle.into()
94}
95
96fn update_complexity(actual_complexity: &mut Option<ComplexityClass>, expected_complexity: &mut Option<ComplexityClass>, puzzle: &Vec<Option<Tile>>, is_not_complex_enough: &mut bool, is_too_complex: &mut bool) {
97  let result = classify_puzzle(&puzzle.clone().into());
98  *actual_complexity = result.ok();
99  *is_not_complex_enough = actual_complexity != expected_complexity;
100  *is_too_complex = actual_complexity.is_some() && actual_complexity.unwrap() > expected_complexity.unwrap();
101
102}
103
104fn reinsert_tile(puzzle: &mut Vec<Option<Tile>>, history: &mut Vec<(Option<Tile>, usize)>) {
105  // println!("Puzzle is not valid reinserting tile");
106  let (removed_tile, removed_position) = history.pop().unwrap();
107  puzzle[removed_position] = removed_tile;
108  // println!("puzzle: {:?}, removed_tile: {:?}, removed_position: {:?}", puzzle, removed_tile, removed_position);
109
110}
111
112fn remove_non_empty_tile(mut puzzle: Vec<Option<Tile>>) -> (Vec<Option<Tile>>, Option<Tile>, Option<usize>) {
113  let mut rng = rand::thread_rng();
114  let mut index = rng.gen_range(0..puzzle.len());
115
116  for _ in 0..10 {
117    if puzzle[index].is_some() {
118      index = rng.gen_range(0..puzzle.len());
119    }
120  }
121
122  while puzzle[index].is_none() {
123      index = (index + 1) % puzzle.len();
124  }
125  let removed_tile = puzzle[index].clone();
126  puzzle[index] = None;
127  (puzzle.clone(), removed_tile, Some(index))
128}
129
130fn create_solution_from_cycle(eulerian_cycle: &Vec<crate::Node>) -> Solution {
131eulerian_cycle
132    .windows(2)
133    .map(|arc| {
134        Tile(
135            arc[0].clone().try_into().unwrap(),
136            arc[1].clone().try_into().unwrap(),
137        )
138    })
139    .collect()
140}
domino_lib/generate/mod.rs

domino_lib/generate/
mod.rs
