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