### Problem Description

.The object of this puzzle is to arrange the
integers 1 through 16 into a 4x4 grid so that the sum of any two cells
horizontally or vertically is prime.

### Background & Techniques

Here is one of the 2992 solutions which can be generated by the
program. Since the only even prime is 2 and the sum of adjacent cells
will always be 3 or greater, all of the prime sums must be odd. And, since
the sum of two even or two odd numbers is always even, it is clear that each
number must have neighbors of the opposite parity. If a row contains
odd-even-odd-even numbers, the row above or below must contain
even-odd-even-odd numbers. The effect is similar to a checkerboard with
number of one parity on the black squares and numbers of the other parity on
the red squares.

No user play is included in the program, so you're on your own if you want
to try discovering a solution without help.
The puzzle was adapted from "The Master Book of Mathematical Recreations",
Fred Schuh, Dover Publications. The book has several pages describing
techniques for finding solutions manually. The book is out of
print, but you can use the Amazon link at left to find used copies.

The program takes advantage of the "checkerboard" arrangement of odds and
evens by permuting the 8
odd numbers into the "odd" positions and for each of those, permuting the 8 even
numbers into the "even" positions and then checking for prime pair sums. For
a second "Solve" button, the odd-even roles are reversed. Note that if the effects
of rotating and mirroring are considered, the number of unique solutions is
reduced by a factor of 8.

Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program.

#### Notes for Programmers

Upon first reading the problem description, it seemed to be quite
trivial, just generate all permutations of the integers 1 to 16 and check the
sums appropriately. For the 12 horizontal
pair sums,( positions 1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15), sum with
the next number and check to see if the sum is prime. For positions 1 through 12, check the
vertical pairs by summing the number in
that position with the one 4 positions later (position 1 + position 5,
pos. 2 + pos 6, etc.).

The problem is that there would be 20 trillion permutations to check (2x10^{13}).
A little further thought made it clear that there is no need to check all
permutations. As explained above, odd and even numbers must be
adjacent, so we can permute the odds and evens separately and insert them in
an array appropriately to perform the sum check. There are "only"
40,000 permutations of 8 objects, so we can get by with checking (4 x
10^{4}) ^{2} = 1.6 x 10^{9 }permutations,
reducing the problem size by a factor of 10,000 and allowing solutions to be
found in a minute or two on a modern computer.

Once an array is ready to be checked, the fastest way turned out to be
testing that a sum was not one of the five non-prime odd numbers between
the smallest sum (1+2=3) and the largest (15+16=31). The
non-primes in this range are 9, 15, 21, 25, and 27. Finding any
of these values among the 24 sums to check allow us to stop checking that
array immediately.

The **MathsLib** unit is included in the downloadable source zip file.
It contains the **NextPermute** function used to generate the
permutations.

### Running/Exploring the Program