summary refs log tree commit diff stats
path: root/Source/Solver.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'Source/Solver.cpp')
-rw-r--r--Source/Solver.cpp76
1 files changed, 76 insertions, 0 deletions
diff --git a/Source/Solver.cpp b/Source/Solver.cpp new file mode 100644 index 0000000..244bfb2 --- /dev/null +++ b/Source/Solver.cpp
@@ -0,0 +1,76 @@
1#include "Solver.h"
2#include "Puzzle.h"
3#include "Validator.h"
4
5std::vector<Puzzle> Solver::Solve(Puzzle& p) {
6 std::vector<Puzzle> solutions;
7 // var start = (new Date()).getTime()
8 for (int x = 0; x < p.width; x++) {
9 for (int y = 0; y < p.height; y++) {
10 Cell cell = p.grid[x][y];
11 if (cell.start) {
12 SolveLoop(p, x, y, solutions);
13 }
14 }
15 }
16 // var end = (new Date()).getTime()
17 // console.info('Solved', puzzle, 'in', (end-start)/1000, 'seconds')
18 return solutions;
19}
20
21void Solver::SolveLoop(Puzzle& p, int x, int y, std::vector<Puzzle>& solutions) {
22 // Stop trying to solve once we reach our goal
23 if (solutions.size() >= MAX_SOLUTIONS) return;
24 Cell cell = p.GetCell(x, y);
25 if (cell.undefined) return;
26 if (cell.gap != Cell::Gap::NONE) return;
27
28 if (p.sym == Puzzle::Symmetry::NONE) {
29 if (cell.color != Cell::Color::NONE) return; // Collided with ourselves
30 p.grid[x][y].color = Cell::Color::BLACK; // Otherwise, mark this cell as visited
31 } else {
32 /*
33 // Get the symmetrical position, and try coloring it
34 auto sym = p.GetSymmetricalPos(x, y);
35 Cell::Color oldColor = p.GetLine(sym.x, sym.y);
36 p.grid[sym.x][sym.y].color = Cell::Color::YELLOW;
37
38 // Collided with ourselves or our reflection
39 if (cell.color != Cell::Color::NONE) {
40 p.grid[sym.x, sym.y].color = oldColor;
41 return;
42 }
43 p.grid[x][y].color = Cell::Color::BLUE; // Otherwise, mark this cell as visited
44 */
45 }
46
47 if (cell.end != Cell::Dir::NONE) {
48 // Reached an endpoint, validate solution and keep going -- there may be other endpoints
49 Validator::Validate(p);
50 if (p.valid) {
51 Puzzle clone = p;
52 solutions.push_back(clone);
53 }
54 }
55
56 // Recursion order (LRUD) is optimized for BL->TR and mid-start puzzles
57 // Extend path left and right
58 if (y % 2 == 0) {
59 SolveLoop(p, x - 1, y, solutions);
60 SolveLoop(p, x + 1, y, solutions);
61 }
62 // Extend path up and down
63 if (x % 2 == 0) {
64 SolveLoop(p, x, y - 1, solutions);
65 SolveLoop(p, x, y + 1, solutions);
66 }
67
68 // Tail recursion: Back out of this cell
69 p.grid[x][y].color = Cell::Color::NONE;
70 if (p.sym != Puzzle::Symmetry::NONE) {
71 /*
72 auto sym = p.GetSymmetricalPos(x, y);
73 p.grid[sym.x][sym.y].color = Cell::Color::NONE;
74 */
75 }
76}