« The results are in! | Main | MovableType maintenance »

The MagicStar revisited

When designing the algorithm to solve the magic star I considered various heuristic and clever methods of cutting down the work required to find every solution. In the end, I feel back to the brute force method since it was a sure-fire way to get all the solutions, and it was only a matter of running it once.

I received an intriguing comment via email from a guy who’d taken on the challenge to build a faster algorithm. He developed a clever Matlab program which finds all 1792 solutions in 48 minutes (improving on my method by something like a phenomenal 1200 fold). As he openly admitted, the implementation was very messy, requiring deep loops and if statements.

Naturally, this was more than enough to put me back on the trail. Using some of the ideas I had considered prior to the brute force method, and combining them with the clever development in the Matlab solution, I set about developing a better solution in C. Typically, my compact idea became a quite bloated once translated to a program, requiring a reasonably deep for loop, but I think it is relatively coherent. It took somewhere around 4 hours, including developing a permutation algorithm to suit my needs (I tried to find one, but failed!). In particular, most published permutation algorithms permute a set of n symbols from a set of n symbols. I needed one which would permute n symbols from N symbols where N>n. This is also called a “variation” instead of a permutation.

And the results? I have done nothing to optimise the algorithm, but I don’t think there’s much need - all 1792 solutions are found and printed out in the same format as the previous algorithm (although not in the same order) in 2 minutes and 5 seconds on my 1.25GHz G4. That’s an improvement of around 29000 times.

The basic method used is to treat the star as a collection of overlapping sums - the first job is to find 4 numbers which add to 34. Only once they are found, another 4 numbers totalling 34 are then searched for, where one number is the same as the previous 4. Because of the way the numbers in the star overlap, the next step only requires finding 2 unique numbers such that 4 numbers total 34. This continues around the star until all positions are filled.

The code is licensed under a Creative Commons license (eg. use as you will, give me credit, don’t be bad).


TrackBack URL for this entry:


Post a comment