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.

anyways, the working solution can be seen here.

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= 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]);

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

sp.innerHTML += 'solved in ' + h.length + ' steps';

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
}
}
}
`

StackExchange Code Review Q#19000, answer score: 2