I’ve recently been hooked on a very simple Android game, called The Grid Master. There’s a 10×10 grid, you pick a starting location, then move 3 cells straight or 2 cells diagonally. You have to fill up the entire grid. Here’s a pen you can try it in:

See the Pen GridMaster by Kjeld Schmidt (@KjeldSchmidt) on CodePen.0

Random clicking quickly yields a result of 80+, a bit of strategy will easily get you into the 90’s. Within an hour or so, I had gotten to 99. But 100 proved elusive. I decided my computer should solve this for me.

To get a sense of how a search should perform, I roughly estimated the solution space: 100 choices for the first move, up to 7 for every following (because at least one of the eight possible moves will be blocked by the previous)

100 x 7^{99} ≈ 50,000 times the number of atoms in the universe. So, that might take a while.

But of course, that is naive: First, only 25 starting positions are relevant, the others are rotationally equivalent. Second, very rarely will 7 moves actually be available – after the first few it’s usually no more than three or four. Third, most decision trees will stop long before we are 99 layers deep, with no valid moves left. Letting my computer randomly choose, most paths end at around 75 layers, many even fewer. So a better approximation is:

25 x 4^{75} ≈ 0.00068 × the number of chess positions. That’s still a lot, but oh well. I’m sure we’ll discover some great optimizations along the way. Let’s go ahead and automate a solution.

To avoid massive memory use, we’ll search depth first. The basic algorithm is simple:

- Start somewhere
- From the list of possible moves, take the first one. Repeat until no moves are possible.
- If solution is found: Celebrate. If not: Go back one step, take next possible move.
- If all moves from this starting position are checked and none resulted in a party, go back to 1, start somewhere else.

Steps 2 and 3 in JS:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
function searchSolution() { var filledCellsCount = GameState.filledCells.length; var state = searchSolution.state || [ 0 ]; state[ filledCellsCount - 1 ] = state[ filledCellsCount - 1 ] || 0; if ( GameState.cellsInRange.length > state[ filledCellsCount - 1 ] ) { GameState.cellsInRange[ state[ filledCellsCount - 1 ] ].htmlElement.onclick(); } else { state[ filledCellsCount - 1 ] = 0; state[ filledCellsCount - 2 ]++; undo(); } searchSolution.state = state; setTimeout( searchSolution, 500 ) } |

Should hopefully be pretty clear. `state`

does nothing more than remember which path along the tree we took. Now we can watch it unfold:

See the Pen GridMaster by Kjeld Schmidt (@KjeldSchmidt) on CodePen.0

It’s fun to watch for a while. The first undo happens at 64, then it keeps bouncing in the 70-80 range.

For **hours. **(or days, weeks… I never ran it long enough to get out of there).

I mean, sure, I artificially limit it to two moves a second, but that’s still stupid slow. Especially when you consider the top right corner.

It’s empty. Look at all fields that could theoretically reach it – they are already blocked. That’s true for several empty cells, but this one is particularly interesting, because it’s been blocked since move 27. 13 seconds into the calculation and the entire path is already worthless. Clearly, we need to check for inaccessible cells and undo as soon as we find one of these. So now we add this more complicated code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
function cellsAreBlocked() { var emptyCells = getEmptyCells(); var moves = GameState.moves; for ( var i = 0; i < emptyCells.length; i++ ) { var emptyCell = emptyCells[i]; var isReachable = false; var row = emptyCell.row; var col = emptyCell.col; for ( var j = 0; j < moves.length; j++ ) { var move = moves[j]; if ( cellExists( row + move.y, col + move.x ) ) { var cellToCheck = cells[ row + move.y ][ col + move.x ]; if ( !cellToCheck.isFilled ) { isReachable = true; } } } if ( !isReachable ) { return true; } } return false; } |

Let’s also reduce the delay between steps from 500ms to 10ms. Result:

See the Pen GridMaster by Kjeld Schmidt (@KjeldSchmidt) on CodePen.0

That’s better, but still, some flaws quickly become obvious. Again, consider the top right corner. Unless you had this article open for days(weeks, months), chances are it’s empty, and there’s only one cell (three down) that is in range. Which itself has only one empty cell in range – the top right corner. So they are unreachable and my solver doesn’t notice it’s already pointless again.

Here’s whats happening in my head right about now: *Okay, so next I basically need to model this entire thing as a graph and at every step, check if it’s connected, if not, undo… Wait. Not *basically. *This IS a graph. I should look for a path that visits each vertex exactly once… oh, that’s just a Hamilton path. I should have realized this hours ago. Oh well…*

A quick refresher on Wikipedia confirms what I now fear: This is, like so many graph problems, in NP. So, basically, it takes very long. Some intense google sessions and a few paper introductions later, I fail to find an efficient deterministic algorithm. Many work only for detecting cycles, rather than paths (which is nowhere near a given with our problem), or only *may *find a solution, if it exists. So before implementing any of those, I’ll continue with the joy of figuring out better ways by myself.

Read more in Part 2 (coming soon™)