Functioning solver/validator (at least for mazes)

1 files changed, 76 insertions, 0 deletions

@@ -0,0 +1,76 @@
+#include "Solver.h"
+#include "Puzzle.h"
+#include "Validator.h"
+
+std::vector<Puzzle> Solver::Solve(Puzzle& p) {
+    std::vector<Puzzle> solutions;
+    // var start = (new Date()).getTime()
+    for (int x = 0; x < p.width; x++) {
+        for (int y = 0; y < p.height; y++) {
+            Cell cell = p.grid[x][y];
+            if (cell.start) {
+                SolveLoop(p, x, y, solutions);
+            }
+        }
+    }
+    // var end = (new Date()).getTime()
+    // console.info('Solved', puzzle, 'in', (end-start)/1000, 'seconds')
+    return solutions;
+}
+
+void Solver::SolveLoop(Puzzle& p, int x, int y, std::vector<Puzzle>& solutions) {
+ // Stop trying to solve once we reach our goal
+    if (solutions.size() >= MAX_SOLUTIONS) return;
+    Cell cell = p.GetCell(x, y);
+    if (cell.undefined) return;
+    if (cell.gap != Cell::Gap::NONE) return;
+
+    if (p.sym == Puzzle::Symmetry::NONE) {
+        if (cell.color != Cell::Color::NONE) return; // Collided with ourselves
+        p.grid[x][y].color = Cell::Color::BLACK; // Otherwise, mark this cell as visited
+    } else {
+        /*
+        // Get the symmetrical position, and try coloring it
+        auto sym = p.GetSymmetricalPos(x, y);
+        Cell::Color oldColor = p.GetLine(sym.x, sym.y);
+        p.grid[sym.x][sym.y].color = Cell::Color::YELLOW;
+
+        // Collided with ourselves or our reflection
+        if (cell.color != Cell::Color::NONE) {
+            p.grid[sym.x, sym.y].color = oldColor;
+            return;
+        }
+        p.grid[x][y].color = Cell::Color::BLUE; // Otherwise, mark this cell as visited
+        */
+    }
+
+    if (cell.end != Cell::Dir::NONE) {
+        // Reached an endpoint, validate solution and keep going -- there may be other endpoints
+        Validator::Validate(p);
+        if (p.valid) {
+            Puzzle clone = p;
+            solutions.push_back(clone);
+        }
+    }
+
+    // Recursion order (LRUD) is optimized for BL->TR and mid-start puzzles
+    // Extend path left and right
+    if (y % 2 == 0) {
+        SolveLoop(p, x - 1, y, solutions);
+        SolveLoop(p, x + 1, y, solutions);
+    }
+    // Extend path up and down
+    if (x % 2 == 0) {
+        SolveLoop(p, x, y - 1, solutions);
+        SolveLoop(p, x, y + 1, solutions);
+    }
+
+    // Tail recursion: Back out of this cell
+    p.grid[x][y].color = Cell::Color::NONE;
+    if (p.sym != Puzzle::Symmetry::NONE) {
+        /*
+        auto sym = p.GetSymmetricalPos(x, y);
+        p.grid[sym.x][sym.y].color = Cell::Color::NONE;
+        */
+    }
+}