domino_lib/validate/
mod.rs

1use model::{compute_model, variables::create_tileset};
2
3use crate::{utils::{get_n, DominoError, Model, Puzzle, ResultTranslator}, Solution, Tile};
4
5mod model;
6
7/// Validates a given puzzle solution by computing a model and checking the objective value.
8///
9/// This function takes a reference to a `Puzzle` and a `Solution`, then performs the following steps:
10/// - Computes a string-based model representation using `compute_model()`.
11/// - Executes the computed model using `Model::execute()`.
12/// - Extracts the objective value from the solver result.
13/// - Compares the objective value against the expected missing tile count.
14/// - Returns `Ok(())` if the objective value matches the missing tile count, otherwise returns a `DominoError`.
15///
16/// # Arguments
17///
18/// * `puzzle` - A reference to the `Puzzle` structure representing the puzzle to be validated.
19/// * `solution` - A reference to the `Solution` structure representing the proposed solution.
20///
21/// # Returns
22///
23/// * `Ok(())` - If the computed objective value matches the expected number of missing tiles.
24/// * `Err(DominoError::ModelError)` - If the model execution fails or the objective value is incorrect.
25///
26/// # Errors
27///
28/// This function returns a `DominoError::ModelError` in the following cases:
29/// - If `compute_model()` returns an error.
30/// - If `Model::execute()` fails to execute the computed model.
31/// - If the extracted objective value does not match the expected missing tile count.
32pub fn validate_puzzle(puzzle: &Puzzle, solution: &Solution) -> Result<(), DominoError> {
33    // Compute a string-based model representation for the puzzle and solution.
34    let string_model = compute_model(puzzle, solution)?;
35    // println!("string_model: {string_model}");
36    // Execute the model to obtain a solver result.
37    let solver_result = Model::execute(string_model.clone());
38
39    // Extract the objective value from the solver result.
40    // May also see the values of the variables through translator._get_variables() method
41    if let Ok(translator) = solver_result {
42        // Count the number of missing tiles in the puzzle.
43        let missing_tiles = puzzle.0.iter().filter(|tile| tile.is_none()).count() as f64;
44
45        // Validate the objective value against the expected missing tiles count.
46        let objective = translator.get_objective();
47        if objective == missing_tiles {
48            Ok(())
49        } else {
50            let solution: Vec<Option<Tile>> = model_solution_parse(translator, puzzle).expect("Failed to parse solution");
51            Err(DominoError::ModelError(
52                  format!("Found another solution: {solution:?}")// with model: {string_model}"),
53              ))
54        }
55    } else {
56        Err(DominoError::ModelError(
57            "Model failed execution".to_string(),
58        ))
59    }
60}
61
62// Function that given the space of tiles existing for a given puzzle and the result of an lp model having as variables names:
63// x_{i,j} where i is the index of the tile in the tileset used and j the position where it got inserted within the puzzle space
64// returns the solution computed by the lp model
65fn model_solution_parse(
66    translator: ResultTranslator,
67    puzzle: &Puzzle,
68) -> Result<Vec<Option<Tile>>, DominoError> {
69    let variables: std::collections::HashMap<String, f64> = translator._get_variables();
70    let n: i32 = get_n(puzzle)?;
71    let tileset: Vec<(usize, usize)> = create_tileset(n as usize);
72    let tileset_digits: usize = (tileset.len() as f32).log10().floor() as usize + 1;
73    let sequence_digits: usize = (puzzle.0.len() as f32).log10().floor() as usize + 1;
74    let mut solution: Vec<Option<Tile>> = puzzle.0.clone();
75    for variable in variables.into_iter().filter(|variable| variable.1 == 1.0) {
76        let variable_label: String = variable.0;
77        let tile_index: usize = variable_label[1..1 + tileset_digits]
78            .parse::<usize>()
79            .unwrap();
80        let position_index: usize = variable_label
81            [1 + tileset_digits..1 + tileset_digits + sequence_digits]
82            .parse::<usize>()
83            .unwrap();
84        solution[position_index] =
85            Some((tileset[tile_index].0 as i32, tileset[tile_index].1 as i32).into());
86    }
87    Ok(solution)
88}
89
90#[cfg(test)]
91mod tests {
92
93    use super::validate_puzzle;
94
95    #[test]
96    fn test_validate_valid_puzzle_with_single_hole() {
97        let puzzle = vec![
98            Some((0, 0).into()),
99            Some((0, 1).into()),
100            Some((1, 1).into()),
101            Some((1, 2).into()),
102            Some((2, 2).into()),
103            None,
104            None,
105            None,
106        ];
107        let solution = vec![
108            (0, 0).into(),
109            (0, 1).into(),
110            (1, 1).into(),
111            (1, 2).into(),
112            (2, 2).into(),
113            (2, 3).into(),
114            (3, 3).into(),
115            (3, 0).into(),
116        ];
117        println!("Testing valid puzzle with single hole: {:?}", puzzle);
118        println!("Solve model:");
119        println!("Validate model:");
120        let result = validate_puzzle(&puzzle.into(), &solution.into());
121        println!("Validation result: {:?}", result);
122        assert!(result.is_ok());
123    }
124
125    #[test]
126    fn test_validate_valid_puzzle_with_multiple_holes() {
127        let puzzle = vec![
128            None,
129            Some((0, 1).into()),
130            None,
131            Some((1, 2).into()),
132            Some((2, 2).into()),
133            None,
134            None,
135            None,
136        ];
137        let solution = vec![
138          (0, 0).into(),
139          (0, 1).into(),
140          (1, 1).into(),
141          (1, 2).into(),
142          (2, 2).into(),
143          (2, 3).into(),
144          (3, 3).into(),
145          (3, 0).into(),
146        ];
147        println!("Testing valid puzzle with multiple holes: {:?}", puzzle);
148        assert!(validate_puzzle(&puzzle.into(), &solution).is_ok());
149    }
150
151    #[test]
152    fn test_validate_empty_puzzle() {
153        let puzzle = vec![];
154        let solution = vec![
155          (0, 0).into(),
156          (0, 1).into(),
157          (1, 1).into(),
158          (1, 2).into(),
159          (2, 2).into(),
160          (2, 3).into(),
161          (3, 3).into(),
162          (3, 0).into(),
163        ];
164        println!("Testing empty puzzle: {:?}", puzzle);
165        let result = validate_puzzle(&puzzle.into(), &solution);
166        println!("Validation result: {:?}", result);
167        assert!(result.is_err());
168    }
169
170    #[test]
171    fn test_validate_double_tiles_no_orientation() {
172        let puzzle = vec![Some((0, 0).into()), None, None, None, None, None, None];
173        let solution = vec![
174          (0, 0).into(),
175          (0, 1).into(),
176          (1, 1).into(),
177          (1, 2).into(),
178          (2, 2).into(),
179          (2, 3).into(),
180          (3, 3).into(),
181          (3, 0).into(),
182        ];
183        println!("Testing double tiles no orientation: {:?}", puzzle);
184        let result = validate_puzzle(&puzzle.into(), &solution);
185        println!("Validation result: {:?}", result);
186        assert!(result.is_err());
187    }
188
189    #[test]
190    fn test_validate_single_tile_orientation() {
191        let puzzle = vec![Some((0, 1).into()), None, None, None, None, None, None];
192        let solution = vec![
193            (0, 1).into(),
194            (1, 1).into(),
195            (1, 2).into(),
196            (2, 2).into(),
197            (2, 3).into(),
198            (3, 3).into(),
199            (3, 0).into(),
200            (0, 0).into(),
201        ];
202        println!("Testing single tile orientation: {:?}", puzzle);
203        let result = validate_puzzle(&puzzle.into(), &solution);
204        println!("Validation result: {:?}", result);
205        assert!(result.is_err());
206    }
207
208    #[test]
209    fn test_validate_invalid_puzzle_empty() {
210        let puzzle = vec![None; 8];
211        let solution = vec![
212            (0, 1).into(),
213            (1, 1).into(),
214            (1, 2).into(),
215            (2, 2).into(),
216            (2, 3).into(),
217            (3, 3).into(),
218            (3, 0).into(),
219            (0, 0).into(),
220        ];
221        println!("Testing invalid empty puzzle: {:?}", puzzle);
222        let result = validate_puzzle(&puzzle.into(), &solution);
223        println!("Validation result: {:?}", result);
224        assert!(result.is_err());
225    }
226
227    #[test]
228    fn test_validate_invalid_puzzle_invalid_size() {
229        let puzzle = vec![None; 9];
230        let result = validate_puzzle(&puzzle.into(), &vec![]);
231        println!("Validation result: {:?}", result);
232        assert!(result.is_err());
233    }
234
235    #[test]
236    fn test_validate_puzzle_with_ambiguous_solution() {
237        let puzzle = vec![
238            Some((0, 0).into()),
239            None,
240            None,
241            None,
242            None,
243            None,
244            None,
245            None,
246        ];
247        let solution = vec![
248          (0, 0).into(),
249          (0, 1).into(),
250          (1, 1).into(),
251          (1, 2).into(),
252          (2, 2).into(),
253          (2, 3).into(),
254          (3, 3).into(),
255          (3, 0).into(),
256        ];
257        println!("Testing puzzle with an ambiguous solution: {:?}", puzzle);
258        let result = validate_puzzle(&puzzle.into(), &solution);
259        println!("Validation result: {:?}", result);
260        assert!(result.is_err());
261    }
262}
domino_lib/validate/mod.rs

domino_lib/validate/
mod.rs
