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)