Solving the 7x7 maze with JS

If you ever find yourself in Chilton Wisconsin with some time to kill I recommend Mauer Farm for an all day family fun. In addition to the corn maze there was also the 7x7 Maze drawn on the ground big enough to walk through the solution. We spent hours trying to solve it. One person even claimed she found the solution but we didn't supervise her closely enough to verify there was no foul play. In other words, this is not an easy puzzle to solve just by looking at it or brute forcing your way through. After getting back home I spent a Saturday at my favorite coffee shop having fun with the solution and I've learned a few things I wanted to share.

maze 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.

Simplify and Solve

Let's start by solving a much simpler puzzle:

221
122
220

This maze can be represented by a directed graph like this:
maze-graph
Notice that nodes are linked with single direction edges.

this is a 5 step solution (there's also a shorter one)

maze-graph-solution

There are also infinite loops to watch out for. In fact there are a lot more infinite loops than there are solutions.

maze-graph-loop

Looking at these flows the solution emerges pretty quickly. All we have to do is follow each path and terminate the ones that return to a previously visited node. That way all loops are terminated, and we are left with solutions that navigated all the way out to the final node in bottom right corner.

First let's define and store the maze. We can do that with a 2 dimensional array like this:


    var _maze = [
        [2,2,1],
        [1,2,2],
        [2,2,0]
      ];

Now we can iterate along x/y axis to retrieve the step number, but for the sake of simplicity later we could store more information in each square such as x/y coordinates


    for (var i=0; i<_maze.length; i++)        // iterate rows
        for (var j=0; j<_maze[i].length; j++) // iterate cols
            // swap value integer with an objct that contains more information. 
            _maze[i][j] = { x: j,             // store X position
                            y: i,             // store Y position
                            v: _maze[i][j],   // store # of steps
                            toString: function(){return '[' + this.x + ':' + this.y + '(' + this.v + ')]';} // neater way to print this node
                           };



After running above code the array gets updated to store objects that look like this.
maze-array-objects
Later when we're passing these objects around they will be more like graph nodes (self aware of their location) than simple value integers.

At this point I encourage you to spend a few hours trying to come up with this solution on your own. All you have to do is iterate over the nodes following all available edges (like the in the flow chart).

Here is my implementation:


  function move(node, direction, history) {
    // 1. create a new copy history array since it gets passed by reference.
    history = history.slice(0); 
    // 2. save current node into current thread history
    history.push(node);
    // 3. get next node
    var nextNode = getNextNode(node, direction);
    if (!nextNode) 
      return; // no node exists at that address
    // 4. check if this node has already been visited. 
    if (history.some(function(o){
      return o == nextNode;
    })){
      return; // loop detected, terminate!
    }
    // 5. check if next node arrives at the solution  
    if (nextNode.v == 0){ 
      history.push(nextNode); // solution found! save to history and exit 
      _solutions.push(history);
      return;
    }
    // attempt to move in every direction
    move(nextNode, 'up', history);
    move(nextNode, 'down', history);
    move(nextNode, 'right', history);
    move(nextNode, 'left', history);
  }
    // ****************** start the program ******************* /
    // take the first node and try going down and right
    var startNode = _maze[0][0];
    move(startNode, 'down', []);  // params: node, direction, history array
    move(startNode, 'right', []);

This is a basic recursive function that traverses the graph in all available directions. I've omitted the other functions for clarity, but you can download a working html file with full implmentation here.

  1. We are exploring many paths in this graph. The point of passing history is to keep track of each individual path. Each time we hit the move() function, we spawn 4 more directions (branches). Since JavaScript passes objects by reference, each new branch will write to the same history, and in the end all paths would include all other paths. array.slice(0) is just a nifty trick to create a copy of the array so that we no longer modify the original.

  2. save this node in history. If this is the right path will need this history to link to the solution

  3. call a utility function that will check if a node exists provided number of steps and the direction. It checks the bounds and and returns a "node" object if one exits. Omitted here but you can see the implementation in the above mentioned source.

  4. history.some(e) is just a shorter way of saying foreach(node) in history check if current node has already been visited/saved. If so a loop is detected and we can terminate the current path. Notice the === operator which verifies both the type and value of each node. In this case both (=== and ==) would work but it is always good to understand this difference and use == only when equivalence check is desired.

  5. check if the next node arrives at the solution. If yes, complete the history by adding the next node and add the history to the collection of correct solutions. now _solutions holds all successful paths.

Performance

If this was an interview you'd probably be asked what can be improved about this algorithm. We applied a Depth-First Search which is pretty standard for navigating tree or graph structures. It works but if we care about the shortest path we won't know which one that is until all paths are found. This could be sped up by using Breadth-First Search which explores all possibilities on lower branches before moving further. This can be useful when your tree/graph is unbalanced and has a wide range of solutions, because it will find shortest path first and it can be terminated after that. Send me a note if interested and I can provide that solution as well, or link to yours!

Another thing to look out for is code like this (from #4):

if (history.some(function(o){ return o === nextNode; })

Each time we check if something exist in history this will do a loop over the whole history and a comparison with each element which can cost up to O(n) time. This could be optimized by storing each history element in a collection that offers O(1) average access time such as a Hashtable (associative array in JS). So above check would become something like this:

if (myHistoryHash[nextNode]) return true; // match found

Another thing to note is that recursive calls can exhaust memory relatively quickly depending on the language (especially if those languages make the heap/stack distinction). Each time we re-enter the function we're creating a new stack frame which then keeps track of a new set of local variables until that frame (function) goes out of scope. Unfortunately none go out of scope until the solution (or termination) happens.

I've implemented these pointers in a new post.

Working Solution

While you've been reading this post your browser has been busy solving the puzzle and the solutions are ready below
*click on solutions to see re-play
*click multiple solutions simultaneously for trippy disco mode

Up Next: Breadth First Solution

[In the next post] (http://rafalbuch.com/cracking-the-mega-maze-using-breadth-first-search/) I outline how to solve this using a faster algorithm along with a more complex maze to solve.