Cracking the Mega Maze using breadth first search

Last week I posted a solution to an award winning 7x7 puzzle using Javascript. It was widely acclaimed and revered (it was read by 2 people) so I decided to follow up by improving upon that solution. An algorithm so good it can bust the mega-fucking-maze.

Mega Maze Demo

The rules again:
You start in upper left corner and each square tells you the exact # of moves you can execute in any direction as long as you stay within bounds. The goal is to get to the bottom right corner.

Implementation

Previous algorithm was fine for 7x7 maze, but since it explores all possible paths it can get slow if there are many options available (not to mention run out of memory since it was recursive), so let's improve it by doing the following:

  1. Provide an imperative implementation (no recursion).
  2. Switch from depth-fist to breadth-first search to optimize for termination after first match is found.
  3. Drink lots of sake during the exercise.

Breadth-First Search

This is a nifty algo to remember for your interview because it can solve many common problems such as termite infestation in your bee shed or a cheating spouse. Ok so i've never actually gotten this problem in an interview yet, but I just know there is a "lead architect" somewhere out there, sitting in a rocking chair in his Vibram shoes, reading latest issue of popular science and someday we will meet, and i'll be ready.

Going back to solving for the simplest case first, here's the trivial maze with 2 simple solutions:

221
122
220

same maze but with numbered squares to help visualize breadth first approach:
small maze numbered

Breadth First Search will navigate it exploring all combination on higher branches before moving lower, and thus a 2 step solution is found quickly.

Here we can see 2 solutions. At 2nd and 5th steps from start.
Since all we care about is one solution the search is terminated after 2nd step. So the only difference is that as we go through each step, all paths are explored within that step before moving on to next step.

Now that we understand the concept, implementation is very simple!

  
  function solve(root){
      var q = new Queue();  // using a Queue library 
      q.enqueue(root);      // Queue is needed in order to ensure that nodes are navigated in order from lowest to higest
      var visited = {};     // will use a hashtable to determine loops. 
      visited[root] = true; // add root node to visited hash

      while (!q.isEmpty()){ // as long as there are nodes in the qeueue let's keep searching
         var node = q.dequeue();
         getAvailableLinks(node).forEach(function(n){ // find all possible edges from current node, and loop through them
             if (visited[n]) return; // loop detected, terminate
             visited[n] = true;
             n.parent = node; // save bread crumbs via linked list 
              if (n.v === 0){ // solution found! 
                  while (!q.isEmpty()) q.dequeue(); // empty the queue 
                  showResults(n);
                  return;
              }
              else // current node is not the solution, add to queue in order to process all edges from this node next! 
                q.enqueue( n );
          });
      }
  }

As in previous post, leaving out all non essential code all of which can be seen/run in a single html file here. It has one dependency Queue.js referenced here.

In this case finding a solution means finding a lower right grid cell (node). After we have that node, we can go back up the tree to show the solution like this:



    function showResults(n) {
        var steps = [n]; 
        while (n){
            n = n.parent; 
            if (n) steps.push(n);
        }
        _solutions = [steps.reverse()];
        writeOutput(_solutions.length + ' solutions found.');
        _solutions.forEach(function(s, i){
        writeOutput('' +
            getMoves(s).length + 
            ' moves: ' +
            s.map(function(el){ return ' ' + el.toString();})) 
        }); 
    }

sake time.