# 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]) {
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. –  Gareth Rees Nov 25 '12 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 ? –  Sonic Soul Nov 25 '12 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. –  Brian Nov 26 '12 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. :) –  David Harkness Nov 27 '12 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 –  Sonic Soul Nov 27 '12 at 3:16
ok good point!.. heheh.. i do see it solved like 10 times now.. and the least steps was 19 :) –  Sonic Soul Nov 27 '12 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. –  Sonic Soul Nov 27 '12 at 3:57
If you're counting the starting square as the first step, I got the same answer as you. –  David Harkness Nov 27 '12 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 –  Sonic Soul Nov 27 '12 at 17:36