# 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.

Image: Harry

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

## How many solutions?

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.

Advertisement:

## Here’s one of the solutions

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