Solving a 7x7 maze puzzle

Question

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<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)

Answer 1

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