## 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.

## Saturday, March 16, 2013

### Solving Aristotle's Number Puzzle

Aristotle's Number Puzzle by Professor Puzzle is number puzzle involving 19 numbers arranged into a hexagon. The goal of the puzzle is to rearrange the numbers so each of the 15 rows add up to 38.

I managed to solve this puzzle by writing a program to iteratively search for the solution. It might be possible to solve the puzzle using only logic and deduction but I have no idea how. Please leave a comment if you've actually solved it that way! The official solution video on YouTube gives the solution but doesn't explain how it was derived.

What follows is a derivation of the program that solves the puzzle. All the code is available on github at aristotle_puzzle.

First, let's get a mathematical description of the problem.

Let the variables `a, b, c, ..., s` represent the values of each cell like this: That gives us these equations:

```a + b + c         = 38
b + e + i + m     = 38
h + i + j + k + l = 38
m + n + o + p     = 38
q + r + s         = 38

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

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

The other constraints are:

• None the values must be equal so `a != b`, `k != q` etc.
• Each value comes from the set `{1, 2, ..., 19}`

One attempt to solve the puzzle would be to take each permutation of `{1, 2, ..., 19}` assign it to `a, b, ..., s` and test the against the constraints until finding all the solutions. The problem is that there are 19! = 1.2e17 permutations so it would take hundreds of years for the program to run.

Going back to the equations, apply Guassian Elimination to attain the following:

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

Python script that derives the above equations.

This gives 7 independent variables: `j, k, n, o, p, r, s` and the equations to generate the remaining 12 dependent ones.

Now, take each permutation of size 7 from `{1, 2, ..., 19}`, assign it to the independent variables, generate the dependent ones and test against the constraints until finding solutions. This should be feasible since there are only 19!/12! = 2.5e8 of these to check.

C program that implements the above procedure

It turns out that are only 12 solutions but they are all rotations and/or mirrors of each other. Here is one of them: 