# Solving a 7x7 maze puzzle

i came across this fun puzzle while being on vacation.

It was designed by Robert Abbott and painted into the grass of a Wisconsin farm. Robert succeeded into making it seem really easy to solve. Well, it is not. I spent hours with my friends wandering the puzzle and left frustrated.

I decided to solve it using computers. chose javascript because it made it easy to visualize the process and solution.

Initially i started with a brute force algorithm, which run for hours and got me nowhere. Than i shifted to this final one (below). I just kinda came up with this recursive solution that explores all paths, and terminates any path that comes across a previously visited node, so the one that makes it to the end should be the shortest one in (my) theory. I am wondering if this is a known algorithm (and how i botched it), and if there is a better way to achieve this. Also this algo appears to find the answer in 28 steps (including entry step).. A friend of mine solved this using an algo that works its way back from the end which supposedly solved it in 20 steps.

here is the recursive function:

_delay = 50;
_successfulSteps = null;
function findRecursive(params){
var cell = params[0];
var steps = params[1];
var history = params[2];
var x = getX(cell);
var y = getY(cell);
var steps = getCellSteps(cell);
markCellActive(x,y);

var h = [];
for (var i = 0; i<history.length; i++) {
h.push(history[i]);
};
h.push([getX(cell),getY(cell)]);

if (steps == 0) {
var sp = \$('#solutionSpan')[0];
sp.innerHTML = 'solved in ' + h.length + ' steps';
return;
}

for (var i = history.length - 1; i >= 0; i--) {
if (x == history[i][0] && y == history[i][1]) {
// this cell already processed
console.log('terminating recursion for: ' + y + ':' + x);
return;
}
};

var rightCell = getRightCell(x,y, steps);
var leftCell = getLeftCell(x,y, steps);
var upCell = getUpCell(x,y, steps);
var downCell = getDownCell(x,y, steps);

// add delay to visualize the process
if (rightCell){
setTimeout(findRecursive, _delay, [rightCell, steps, h]);
}
if (leftCell){
setTimeout(findRecursive, _delay, [leftCell, steps, h]);
}
if (upCell){
setTimeout(findRecursive, _delay, [upCell, steps, h]);
}
if (downCell){
setTimeout(findRecursive, _delay, [downCell, steps, h]);
}

}


(i should note that this is not the prettiest code and i'm not looking for a way to reduce # of lines or anything, just to find a better algorithm)

• The shortest path problem can be solved using Dijkstra's algorithm. Commented Nov 25, 2012 at 20:56
• since each node is forcing a # of subsequent steps, i believe it's not as simple as finding the least # of steps between 2 points. Those steps are already routed and the problem is finding that route. is that still the same as shortest path problem ? Commented Nov 25, 2012 at 23:06
• @SonicSoul: Yes. This puzzle can be represented as a directed graph. Each node has a directed edge to each node that is N spaces away. Commented Nov 26, 2012 at 16:03
• Thanks for the cool puzzle. I am learning Scala and just completed an exhaustive, breadth-first search algorithm. I'm pretty sure it's ten times as long as it needs to be. :) Commented Nov 27, 2012 at 3:29

You're finding all solutions, but because the code overwrites the <span> for every solution found you only see the last one. Try this:

sp.innerHTML += 'solved in ' + h.length + ' steps<br/>';


You're performing a breadth-first search of all possible paths through the maze which is what I ended up going with. By scheduling timer events you're essentially queueing up cells. I did the same but with an actual queue of cells to visit.

This is the core of my Scala version.

// pathTo tracks the best path to each point
// moves(Point) returns the number in that cell

val queue = new Queue[Point]
queue enqueue new Point(0, 0)  // start from top-left
while (!queue.isEmpty) {
val start = queue dequeue
val path = pathTo(start)
(UP, DOWN, LEFT, RIGHT) foreach { direction =>
val end = start.move(direction, moves(start))
if (end != None && !pathTo.contains(end)) {
pathTo(end) = path + end
queue enqueue end
}
}
}

• actually i don't stop after first solution. if any others were found, it should print it again.. although that has not happened, but technically the code is not stopping after first success Commented Nov 27, 2012 at 3:16
• ok good point!.. heheh.. i do see it solved like 10 times now.. and the least steps was 19 :) Commented Nov 27, 2012 at 3:32
• i kind of assumed i'd see the span rewrite, since i had that delay.. but the delay was not big enough to notice the rewrites. Commented Nov 27, 2012 at 3:57
• If you're counting the starting square as the first step, I got the same answer as you. Commented Nov 27, 2012 at 7:33
• well my question was more about figuring out if this is the best algorithm.. if if there is a better way to find the answer.. but i'll accept if there arent any other suggestions Commented Nov 27, 2012 at 17:36