1. 14
evoniuk.github.io
1.

2. 2

To summarize, the author describes a brute-force solution. Their program uses depth-first search to generate all possible paths through the level that don’t retread ground, and for each path, it evaluates whether it is a valid solution.

I can imagine possible optimizations, such as terminating searches starting from paths that pass the goal without having stepped on every tile. I was curious exactly how slow this brute-force algorithm was without those optimizations, so I did some benchmarking.

First, so I could have a larger puzzle to test with, I made up a custom puzzle with a 7×10 grid. See if you can solve it by eye! Start at the bottom center `▪︎` and go to the top center `▪︎` via all `▫︎`.

``````▫︎  ▫︎  ▫︎  ▪︎  ▫︎  ▫︎  ▫︎
▫︎  ▲  ▫︎  ▫︎  ▫︎  ▲  ▫︎
▫︎  ▫︎  ▫︎  ▲  ▲  ▫︎  ▫︎
▫︎  ▫︎  ▫︎  ▫︎  ▫︎  ▫︎  ▲
▫︎  ▲  ▫︎  ▫︎  ▲  ▫︎  ▫︎
▫︎  ▫︎  ▫︎  ▫︎  ▫︎  ▫︎  ▫︎
▫︎  ▫︎  ▲  ▫︎  ▫︎  ▲  ▫︎
▫︎  ▫︎  ▫︎  ▫︎  ▫︎  ▲  ▫︎
▫︎  ▲  ▲  ▲  ▫︎  ▫︎  ▫︎
▫︎  ▫︎  ▫︎  ▪︎  ▫︎  ▫︎  ▲
``````

I added this puzzle and some test code to `sootopolis.js`:

``````const roryCustomPuzzle = [
[0, 0, 0, 0, 0, 0, 0,],
[0, 1, 0, 0, 0, 1, 0,],
[0, 0, 0, 1, 1, 0, 0,],
[0, 0, 0, 0, 0, 0, 1,],
[0, 1, 0, 0, 1, 0, 0,],
[0, 0, 0, 0, 0, 0, 0,],
[0, 0, 1, 0, 0, 1, 0,],
[0, 0, 0, 0, 0, 1, 0,],
[0, 1, 1, 1, 0, 0, 0,],
[0, 0, 0, 0, 0, 0, 1,],
];

const solutions = findSolutions(roryCustomPuzzle);
console.log(solutions);
console.log(solutions.length);
``````

When run with `time node sootopolis.js` on my computer, the program finishes in 7.7 seconds, printing out 38 valid solutions. In comparison, solving `thirdPuzzle` takes 2.8 seconds, solving `thirdEmeraldPuzzle` takes 0.3 seconds, and solving `firstPuzzle` takes 0.1 seconds.

My conclusion? The program, despite using brute force, is still practical for helping a stuck player get past a 7×10 puzzle with 56 traversable tiles. I think the time the program takes to finish for different puzzles could be estimated based on the number of traversable tiles in the puzzle, but I didn’t bother making a plot of runtime vs. traversable tile count.