pentomino/
pentomino.rs

1use std::error::Error;
2use std::time::Instant;
3use exact_cover::vector::Vector2D;
4use exact_cover::problems::polyomino::{Polyomino, PolyominoPacking, Board, CompoundName};
5use exact_cover::{Solver, SolverEvent};
6
7fn print_sol(prob: &PolyominoPacking<&str>, sol: &Vec<CompoundName<&str>>) {
8    let mut buff = Vec::new();
9    
10    for y in 0..prob.board().size().y {
11        let row: Vec<char> = prob.board().cells()[y as usize].iter()
12            .map(|c| { if *c { '.' } else { ' ' } })
13            .collect();
14        buff.push(row);
15    }
16
17    for &(name, o, t) in sol {
18        let cells = prob.pieces()[name].orient(o).translated_cells(t);
19        for Vector2D { x, y } in cells {
20            buff[y as usize][x as usize] = name.chars().nth(0).unwrap();
21        }
22    }
23
24    for y in 0..buff.len() {
25        for x in 0..buff[y].len() {
26            print!("{} ", buff[y][x]);
27        }
28        println!();
29    }
30}
31
32fn main() -> Result<(), Box<dyn Error>> {
33    let board = Board::from_bytes_array(&[
34        b"........",
35        b"........",
36        b"........",
37        b"...##...",
38        b"...##...",
39        b"........",
40        b"........",
41        b"........",
42    ]);
43
44    let pento_f = Polyomino::from_bytes_array(&[
45        b".##",
46        b"##.",
47        b".#.",
48    ])?;
49    let pento_i = Polyomino::from_bytes_array(&[
50        b"#####",
51    ])?;
52    let pento_l = Polyomino::from_bytes_array(&[
53        b"####",
54        b"#...",
55    ])?;
56    let pento_n = Polyomino::from_bytes_array(&[
57        b".###",
58        b"##..",
59    ])?;
60    let pento_p = Polyomino::from_bytes_array(&[
61        b"###",
62        b".##",
63    ])?;
64    let pento_t = Polyomino::from_bytes_array(&[
65        b"###",
66        b".#.",
67        b".#.",
68    ])?;
69    let pento_u = Polyomino::from_bytes_array(&[
70        b"#.#",
71        b"###",
72    ])?;
73    let pento_v = Polyomino::from_bytes_array(&[
74        b"#..",
75        b"#..",
76        b"###",
77    ])?;
78    let pento_w = Polyomino::from_bytes_array(&[
79        b"#..",
80        b"##.",
81        b".##",
82    ])?;
83    let pento_x = Polyomino::from_bytes_array(&[
84        b".#.",
85        b"###",
86        b".#.",
87    ])?;
88    let pento_y = Polyomino::from_bytes_array(&[
89        b"####",
90        b".#..",
91    ])?;
92    let pento_z = Polyomino::from_bytes_array(&[
93        b"##.",
94        b".#.",
95        b".##",
96    ])?;
97    
98    let mut prob = PolyominoPacking::default();
99    *prob.board_mut() = board;
100    prob.add_piece("F", pento_f);
101    prob.add_piece("I", pento_i);
102    prob.add_piece("L", pento_l);
103    prob.add_piece("N", pento_n);
104    prob.add_piece("P", pento_p);
105    prob.add_piece("T", pento_t);
106    prob.add_piece("U", pento_u);
107    prob.add_piece("V", pento_v);
108    prob.add_piece("W", pento_w);
109    prob.add_piece("X", pento_x);
110    prob.add_piece("Y", pento_y);
111    prob.add_piece("Z", pento_z);
112    
113    println!("Generating the problem...");
114    let gen_prob = prob.generate_problem();
115    let mut solver = Solver::new(gen_prob);
116    
117    println!("Solving the problem...");
118    let start_time = Instant::now();
119    let mut solutions = vec![];
120    solver.run();
121    
122    for event in solver {
123        if let SolverEvent::SolutionFound(sol) = event {
124            print_sol(&prob, &sol);
125            println!();
126            solutions.push(sol);
127        }
128    }
129
130    // This does not measure the exact time because printing the solutions takes up a nonnegligible fraction.
131    // To measure the exact time, print the solutions after this line.
132    let elapsed_time = start_time.elapsed();
133
134    println!(
135        "Found {:?} solutions, w/ rotations/reflections. ({:?}s)",
136        solutions.len(),
137        elapsed_time.as_millis() as f64 / 1000.
138    );
139
140    Ok(())
141}
142
pentomino/pentomino.rs

pentomino/
pentomino.rs
