Arranging numbers in a grid: Solution

by David Radcliffe

In a previous post, I described the problem of counting arrangements of the numbers 1 through 16 in a 4×4 grid so that squares with consecutive numbers never touch, even at a corner.

This is a difficult problem, because the set of solutions has little obvious structure. It seems unlikely that a simple formula would exist. On the other hand, naive brute-force is not effective, because there are 16! = 20,922,789,888,000 permutations. Even using a computer, this is too many possibilities to check.

The Monte Carlo method is an effective way to estimate the number of solutions. We simply generate a large number of random arrangements, and count the arrangements which have no consecutive numbers touching.  When I ran this simulation with one million trials, there were 838 successes; so the estimated total number of solutions is 16! * 838 * 10^-6, which is approximately 17.5 billion.

But I wanted to find the exact number of solutions. After several failed attempts, I settled on a divide-and-conquer algorithm.

For each partition {A, B} of the set {1,2,…,16} into two subsets of equal size, find all valid arrangements of A into the top half of the grid, and find all arrangements of B into the bottom half of the grid. Then we add up the pairs of arrangements that are compatible. An important fact is that compatibility is determined by the two middle rows, so we can “lump” some of the 4×2 arrangements together.

The final answer is 17,464,199,440, which is suspiciously close to the Monte Carlo estimate (other runs were not as close). My Python code is available here.

Advertisements