3 files changed, 133 insertions, 9 deletions

diff --git a/examples/puzzle-a-day.rs b/examples/puzzle-a-day.rs
index 6577ede..0fd0877 100644
--- a/examples/puzzle-a-day.rs
+++ b/examples/puzzle-a-day.rs
@@ -1,4 +1,4 @@
-use calendar_puzzle::{CalanderPuzzle, rectangular::{Coords, Piece, Puzzle}};
+use calendar_puzzle::{CalendarPuzzle, rectangular::{Coords, Piece, Puzzle}};
 
 fn main() {
     // construct board coordinates
@@ -83,4 +83,7 @@ fn main() {
             println!("");
         }
     }
+
+    let solutions = puzzle.solve(true);
+    println!("Number of solutions: {}", solutions.len());
 }
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);
+            }
+        }
+    }
+}
diff --git a/src/rectangular.rs b/src/rectangular.rs
index b1c4a23..8dcfa8b 100644
--- a/src/rectangular.rs
+++ b/src/rectangular.rs
@@ -2,7 +2,7 @@ use std::collections::{HashMap, HashSet};
 
 use bitvec::{bitvec, order::Lsb0, vec::BitVec};
 
-use crate::CalanderPuzzle;
+use crate::{CalendarBoardState, CalendarPuzzle};
 
 // clockwise
 #[derive(Clone, Copy)]
@@ -205,6 +205,10 @@ impl Puzzle {
     }
 }
 
+pub struct BoardState {
+    bitvec: BitVec<u64>,
+}
+
 pub struct Placement {
     bitvec: BitVec<u64>,
 }
@@ -215,9 +219,88 @@ impl Placement {
     }
 }
 
-impl CalanderPuzzle for Puzzle {
+fn intersects(a: &BitVec<u64>, b: &BitVec<u64>) -> bool {
+    match (a.domain(), b.domain()) {
+        (bitvec::domain::Domain::Region {head: ha, body: ba, tail: ta},
+         bitvec::domain::Domain::Region {head: hb, body: bb, tail: tb}) => {
+            if let (Some(ha), Some(hb)) = (ha, hb) {
+                if ha.load_value() & hb.load_value() != 0 {
+                    return true;
+                }
+            };
+
+            if ba.iter().zip(bb.iter()).any(|(a, b)| a & b != 0) {
+                return true;
+            }
+
+            if let (Some(ta), Some(tb)) = (ta, tb) {
+                if ta.load_value() & tb.load_value() != 0 {
+                    return true;
+                }
+            };
+
+            return false;
+        },
+        _ => {
+            a.iter().by_vals().zip(b.iter().by_vals()).any(|(a,b)| a && b)
+        },
+    }
+}
+
+fn contains(a: &BitVec<u64>, b: &BitVec<u64>) -> bool {
+    match (a.domain(), b.domain()) {
+        (bitvec::domain::Domain::Region {head: ha, body: ba, tail: ta},
+         bitvec::domain::Domain::Region {head: hb, body: bb, tail: tb}) => {
+            if let (Some(ha), Some(hb)) = (ha, hb) {
+                if !ha.load_value() & hb.load_value() != 0 {
+                    return false;
+                }
+            };
+
+            if ba.iter().zip(bb.iter()).any(|(a, b)| !a & b != 0) {
+                return false;
+            }
+
+            if let (Some(ta), Some(tb)) = (ta, tb) {
+                if !ta.load_value() & tb.load_value() != 0 {
+                    return false;
+                }
+            };
+
+            return true;
+        },
+        _ => {
+            a.iter().by_vals().zip(b.iter().by_vals()).any(|(a,b)| a || !b)
+        },
+    }
+}
+
+impl CalendarBoardState for BoardState {
     type Placement = Placement;
 
+    fn add_placement(&mut self, placement: &Self::Placement) -> bool {
+        if intersects(&self.bitvec, &placement.bitvec) {
+            false
+        } else {
+            self.bitvec |= &placement.bitvec;
+            true
+        }
+    }
+
+    fn remove_placement(&mut self, placement: &Self::Placement) -> bool {
+        if contains(&self.bitvec, &placement.bitvec) {
+            self.bitvec ^= &placement.bitvec;
+            true
+        } else {
+            false
+        }
+    }
+}
+
+impl CalendarPuzzle for Puzzle {
+    type Placement = Placement;
+    type BoardState = BoardState;
+
     fn placements(&self, allow_flips: bool) -> Vec<Vec<Placement>> {
         // TODO remove identical placements
         let orientations = if allow_flips {
@@ -280,5 +363,10 @@ impl CalanderPuzzle for Puzzle {
         }
         placements
     }
+
+    fn empty_board_state(&self) -> BoardState {
+        BoardState { bitvec: bitvec![u64, Lsb0; 0; self.board.len()] }
+    }
 }
 
+