1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
pub mod rectangular;
pub trait CalendarBoardState {
type Placement;
fn add_placement(&mut self, placement: &Self::Placement) -> bool;
fn remove_placement(&mut self, placement: &Self::Placement) -> bool;
}
pub trait CalendarPuzzle {
type Placement;
type BoardState: CalendarBoardState<Placement=Self::Placement>;
fn placements(&self, allow_flips: bool) -> Vec<Vec<Self::Placement>>;
fn empty_board_state(&self) -> Self::BoardState;
fn solve(&self, allow_flips: bool) -> Vec<Vec<usize>> {
let placements = self.placements(allow_flips);
let mut state = self.empty_board_state();
let mut solutions = Vec::new();
backtrack(&mut state, &mut Vec::new(), &placements, &mut solutions);
solutions
}
}
fn backtrack<P, B>(
board_state: &mut B,
stack: &mut Vec<usize>,
placements: &Vec<Vec<P>>,
solutions: &mut Vec<Vec<usize>>,
)
where B: CalendarBoardState<Placement=P> {
let piece_index = stack.len();
println!("{:?}", stack);
if piece_index >= placements.len() {
solutions.push(stack.clone());
} else {
for (i, placement) in placements[piece_index].iter().enumerate() {
if board_state.add_placement(placement) {
stack.push(i);
backtrack(board_state, stack, placements, solutions);
stack.pop();
board_state.remove_placement(placement);
}
}
}
}
|
