1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include "pch.h"
#include "Solver.h"
#include "Validator.h"
int Solver::MAX_SOLUTIONS = 10000;
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.symmetry == 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
p.sequence.emplace_back(x, y);
} 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;
p.sequence.pop_back();
if (p.symmetry != Puzzle::Symmetry::NONE) {
auto sym = p.GetSymmetricalPos(x, y);
p.grid[sym.x][sym.y].color = Cell::Color::NONE;
}
}
|
