The results are in!

One of the fill-in-time puzzles at pub trivia the other week was a fairly benign looking magic star puzzle. The particular configuration that was presented is called "Order 8a" and looks like this: The object is to place the numbers 1 to 16 in the squares such that the total of the four numbers along each line is the same.

The problem seems quite logical, and I figured a bit of sensible number distribution ought to allow me to work towards a solution. A good number of failed attempts later, the puzzle's elusive solution beckoned some further exploration.

In summary, I eventually found there are more than a thousand solutions, but there are more than 20 million million possible combinations of numbers in the star pattern. Since it is the "order" of the numbers in the star that matters, each unique combination is more correctly called a permutation. On a modern computer, it would take about 30 days to iterate through every permutation. The benign looking puzzler turns out to be quite the devilish challenge!

 I really do mean a million million - that is, a one followed by 12 zeros. Unfortunately the useful and logical British notion of a billion equalling a million million has been retired in even the British legal and political documents in favour of the odd notion that a billion equals a thousand million - I'll be explicit above a million to avoid the ambiguity.

Read on for the details of my exploration into the solution space.

Firstly, it helps in solving the puzzle if the number that each line will add up to is known beforehand. There are a few ways to figure this out - some more fortunate than scientific, but this is the method which I find particularly ingenious:

Name the positions in the star a, b, c, d, e, f, g, h, i, j, k, l, m, n, o and p. We know that the sum of all these variables is the same as the sum of the numbers from 1 to 16. That is, 136. We also know that various combinations of them total some number (the very number we are trying to find, call it N). For example:

b + c + d + e = N
h + f + c + a = N
a + d + g + i = N

and so on.

If one were to solve these as a system of linear equations, which is trivially achieved by subtracting the 16 variable sum from the addition of all the 4 variable sums, one would find that N = 34.

Evening after this calculation, and after examining a few of the solutions to the puzzle I found published in various places, I was still none the wiser as to how they might be logically obtained. What interested me was that there appeared to be no patterns amonst the solutions, nor any apparent order within each solution. Naturally then, I set about producing the entire solution set. I'd been curious about permutation iteration algorithms a few times in the past, and coming up with a method for finding every solution allowed me to revisit this curiousity. After evaluating various algorithms, profiling them and optimizing them I settled on the following brute-force algorithm.

for(index=0; index<16; index++)
entries[index] = index+1;

for(iteration=1; 1; iteration++)
{
if(solutionFound(entries))
printSolution(entries);
getNextPermutation(entries);
}

where getNextPermutation looks like this:

void getNextPermutation(int entries[])
{
int i = N - 1;
while (entries[i-1] >= entries[i])
i--;

int j = N-1, entry = entries[i-1];
while (entries[j] <= entry)
j--;
j++;

swap(i-1, j-1);
i++; j = N;

while (i < j)
{
swap(i-1, j-1);
i++;
j--;
}

My actual implementation was modified for speed and to suit the G4 processor, but the algorithm is the same. The algorithm represents the 16 places on the magic star by a one-dimensional array of length 16 (entries). The array is prefilled with the numbers 1 to 16 in ascending order. The algorithm then checks each permutation, iterating through the permutations in lexicographic order. This order allowed me to observe the complete distribution of solutions as they are found, as well as allowing termination halfway through the permutations by taking advantage of the symmetry of the solution space.

Several weeks ago I started this computer off on its solution finding journey. It ran constantly over those weeks, including consuming the background cycles while I interacted with the computer. A few days ago the algorithm finished reporting the first half of the solutions (remember the solutions are symmetrical). I then spent a little time interpreting the results and drawing some conclusions. This is what I found:

• The first solution was found after 30 877 819 664 iterations.
• The 896th solution was found after 10 426 916 886 748 iterations.
• In entirety, there are precisely twice that many solutions, giving a total of 1792 solutions.
• The solutions represent less than 8.6x10-9 percent of the possible permutations.
• In other words, there is slightly better than one chance in 12 thousand million that you would randomly guess a solution.
• If you were to randomly guess a unique permutation once every second, it could take 380 years before you happen across a solution.
• For each number in the top star position, there is an average of 112 solutions. But there could be as few as 90 solutions or as many as 132.
• In fact, many of the solutions are the same. Each solution has 7 rotations which will also be solutions. This reduces our number of unique solutions to 224. Further, for every solution, its mirror is also a solution. This reduces our number to the actual number of unique solutions to the order 8a magic star: 112.

The following graph, produced in AppleWorks, shows at which iteration of the algorithm each of the first 896 solutions were found. The next 896 solutions would be a mirror of this pattern. Notice there are no clear patterns, apart from a vaguely fading set of steep rise/plateau patterns. The following graph, produced in R, shows the number of solutions given the number in the top position of the star. The remaining numbers 9 through 16 would mirror these results. Notice no particular pattern appears. Finally, here's a text file with the raw results. And this is the Perl program I used to parse the numbers from that file:

#!/usr/bin/env perl -w

use strict;
use IO::File;

my \$in = new IO::File "solutions.data"
or die "Unable to open the data file: \$!\n";

my \$count = 0;

while (<\$in>)
{
next if /^\*/;     # skip "***"
my @tokens = split;
foreach (@tokens)
{
if(/\d+/)
{
print; print "\t";
\$count++;
}
}
if(\$count==18)
{
print "\b\n";
\$count = 0;
}
}
\$in->close;

And thus concludes my analysis for the moment.

I discuss a more efficient algorithm here: http://heath.hrsoftworks.net/archives/000074.html

I don't code, so I am not sure if any of this will be useful.

There is an absolute symmetry here. It makes no difference where the first number is placed (the diagram can sort of be turned inside out to create a transformed version of itself - a corner can become a middle and its connections will remain unchanged)

I propose to place one element, WLOG, and then place the rest of the two rows it is part of, also WLOG, and then brute force the remaining 9 elements. The first of the two rows may be placed in arbitrary order, but the second must be permuted.

Using 1 as the arbitrary element, there are only 19 rows that end in 1:

1-16-15-2
1-16-14-3
1-16-13-4
1-16-12-5
1-16-11-6
1-16-10-7
1-16-9-8
1-15-14-4
1-15-13-5
1-15-12-6
1-15-11-7
1-15-10-8
1-14-13-6
1-14-12-7
1-14-11-8
1-14-10-9
1-13-12-8
1-13-11-9
1-12-11-10

If we consider the first of these, then we have (with 6 permutations each):

6-13-14-1-16-15-2
7-12-14-1-16-15-2
8-11-14-1-16-15-2
9-10-14-1-16-15-2
8-12-13-1-16-15-2
9-11-13-1-16-15-2
10-11-12-1-16-15-2

or 42 permutations. We could thus start with less than 10^3 ways to fill 7 slots, leaving 9 to be ground out brute force.

Or have I entirely missed the point? (quite possible!!)