1 files changed, 39 insertions, 6 deletions

diff --git a/src/lib.rs b/src/lib.rs
index 23a954e..3a102c3 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -1,16 +1,49 @@
 pub mod rectangular;
 
-pub trait CalanderPuzzle {
+pub trait CalendarBoardState {
     type Placement;
+    fn add_placement(&mut self, placement: &Self::Placement) -> bool;
+    fn remove_placement(&mut self, placement: &Self::Placement) -> bool;
+}
 
-    // returns a Vec that associates with each piece index,
-    // a Vec of possible placements of that piece
+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) {
+    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);
+            }
+        }
+    }
+}