The sledgehammer and the nut

I’m a little embarrassed. I heard a puzzle last night and thought “Hey, that sounds like a fun puzzle, I can write some clever code to solve this”, and so I did …

I should probably not have done!

The puzzle is pretty easy to describe: You have to place the numbers 1–16 into a 4x4 grid so that no adjacent number is touching. (My interpretation of ‘adjacent number’ included diagonally adjacent as well as orthogonally adjacent). For instance, in the example below, this is not a solution because 6 and 7 are adjacent (as are 14 and 15).

If you want to solve this problem with brute force, you’re going to have a very bad day (in fact a very bad month). There are 16! possible distinct ways to arrange the digit 1–16 into a grid, that’s 20,922,789,888,000. That will take a while to test. However, you never need to explore the vast majority of these permutations because you build up to a solution square by square and, as soon as you hit a constraint, you stop (no point in going on), and truncate a huge amount of the tree. Using a technique called recursive backtracking, you can massively reduce the solution space and solve really quickly. I used this algorithm for full effect when I coded up my Suduko Solver. The technique works by performing a depth-first recursive dive into the problem and, as soon as it finds a block, stops exploring down, backs-up and tries the next branch higher up the tree.

I dutifully coded up a recursive backtracking solver and ran it and, within a blink on a eye, I obtained a solution (cool) … and another, and other. Tens of thousands of solutions scrolled up my screen. All valid.

It’s at this point I engaged my brain and thought about it. Of course! there are lots of solutions. It’s a trivially easy little puzzle, probably aimed simply as an exercise to keep a kindergartner amused for a few minutes. I was so eager to bust out the big guns that I didn’t even attempt to think about it or even try the puzzle on paper.

There’s a moral hidden somewhere in this confession.

I’d used a proverbial sledgehammer to crack a nut.

Now that I’d gone this far into writing unnecessary code, there was no reason to stop. To get an estimate as to the total number of solutions, I used Monte Carlo simulation to randomly shuffle the grid (Using a Fisher-Yates shuffle). For a hundred million random grids, I obtained 83,534 grids which were solutions, giving a success ratio of 0.083534%

Multiplying this by 16! gives the estimate that are approximately 17.5 billion solutions.

Here’s just one of these 17.5 billion solutions. It should not be hard to find a few more!