Sunday, March 31, 2013

Solving Aristotle's Number Puzzle Faster

In my last past, I gave a method for solving the Aristole number puzzle by iterating the 19!/12! permutations of 7 variables from {1, 2, ..., 19 }. The problem with this method is that most of the solutions it finds are just rotations or mirrors of solutions already found.

A more efficient method would be to only look for solutions in a standard orientation so that rotations and mirrors aren't found. (We can rotate and mirror those solutions later if we want to see all the solutions.) Since there 6 ways to rotate the board and 2 ways to "mirror", we'd only have to test 1/12th of the permutations we were checking before.

Use a, c, h, l, o, q, s for the starting variables. The standard rotation we'll use is for to a to be the smallest of the corner hexes on the border so a = min ({a, c, h, l, q, s}). Also require that h < c, which takes care of mirrors.

Now assign a, c, h, l, o, q, s each permutation of 7 from {1, 2, ..., 19} subject to the above constraints and test as before using these equations.

b = 38 - a - c
g = 38 - c - l
p = 38 - l - s
r = 38 - q - s
m = 38 - q - h
d = 38 - h - a
n = 38 - m - o - p
i = 38 - d - n - r
e = 38 - b - i - m
f = 38 - g - e - d
k = 38 - p - f - b
j = 38 - h - i - k - l

C program that implements the above procedure

The C program above finds all the solutions in around 1 second on my laptop.


Unknown said...

19!/12! is 253,955,520, and 1/12 of that is 21,162,960. I took the approach of assigning one puzzle piece at a time, so I could find failed attempts before working out the entire permutation. In other words, I'd assign a and b, which forces c, then assign g which forces l, but if there was no value for l, I'd go to the next value for b. And so on through the puzzle. This saved considerable time, with only 743,650 attempts needed to find all solutions. The first solution was found after 27,440 attempts.

On a base model 2009 Mac mini running Java, execution time to find and display first solution was typically about 20 ms.

Unknown said...

Lol right but how would you solve it without using a computer to do the work for you?

Unknown said...

Does anyone know how to cite this blog? I'm a math PhD student at Cornell and I'm writing a paper for Bridges ( which has to do with this puzzle.