1. 14
  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.