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:

8 comments:

AnonDB said...
This comment has been removed by the author.
Daniel Winsor said...

I too thought of writing a program to do it, but wanted to solve it more logically. After all, Aristotle had not access to the magicks we have.

Each row adds up to an even number, so each row has an even number of odds in it. Finding those configurations is an interesting subproblem - I found [redacted] of them (not counting rotations and mirrors).

Also logically we can cut down on the number of permutations by finding that [redacted] can never be on the corners, and [redacted] cannot be on a corner adjacent to four odds.

Then it was just a matter of trial and error, methodically going through the configurations. One strategy was to eliminate numbers from a certain position. I eliminated entirely 1 configuration very easily, another was hard, and was working on a few when I found the solution. Which of these configurations turned out to be right is very elegant.

It's a pity there are only 12 solutions; I was hoping for more and that led me here.

Treats said...

I used Python to solve this. You're reduced equations really helped and the code you used to derive it seems very elegant!

Here is my code that too 1 hour 3 minutes to work through, although all 12 solutions were found in under 30 minutes: https://github.com/tsunamitreats/aristotlesNumberGame/blob/master/equationPerms.py

Treats said...

I used Python to solve this. You're reduced equations really helped and the code you used to derive it seems very elegant!

Here is my code that too 1 hour 3 minutes to work through, although all 12 solutions were found in under 30 minutes: https://github.com/tsunamitreats/aristotlesNumberGame/blob/master/equationPerms.py

Paul Asimow said...

My recursive program in C took less than a second to find all 12 solutions, without using the reduced equations. Not clear why this should take an hour! I don't think it's Python vs. C. I think it is that the recursive search is very efficient. Not a lot of comments here, but this is the code (this version only prints the first solution, which is fine since they are all equivalent);

//
// main.c
// Aristotle Solver
//
// Created by Paul Asimow on 1/1/15.
// Copyright (c) 2015 Paul Asimow. All rights reserved.
//

#include
int a[19];
int tiles[20];
int fill[15];
int sums[15];

// 0 1 2
// 11 12 13 3
// 10 17 18 14 4
// 9 16 15 5
// 8 7 6


void fillfill(void) {
fill[0] = (a[0] && a[1] && a[2]);
fill[1] = (a[2] && a[3] && a[4]);
fill[2] = (a[4] && a[5] && a[6]);
fill[3] = (a[6] && a[7] && a[8]);
fill[4] = (a[8] && a[9] && a[10]);
fill[5] = (a[10] && a[11] && a[0]);
fill[6] = (a[11] && a[12] && a[13] && a[3]);
fill[7] = (a[9] && a[16] && a[15] && a[5]);
fill[8] = (a[1] && a[13] && a[14] && a[5]);
fill[9] = (a[11] && a[17] && a[16] && a[7]);
fill[10] = (a[1] && a[12] && a[17] && a[9]);
fill[11] = (a[3] && a[14] && a[15] && a[7]);
fill[12] = (a[0] && a[12] && a[18] && a[15] && a[6]);
fill[13] = (a[2] && a[13] && a[18] && a[16] && a[8]);
fill[14] = (a[10] && a[17] && a[18] && a[14] && a[4]);
}

void fillsums(void) {
sums[0] = (a[0] + a[1] + a[2]);
sums[1] = (a[2] + a[3] + a[4]);
sums[2] = (a[4] + a[5] + a[6]);
sums[3] = (a[6] + a[7] + a[8]);
sums[4] = (a[8] + a[9] + a[10]);
sums[5] = (a[10] + a[11] + a[0]);
sums[6] = (a[11] + a[12] + a[13] + a[3]);
sums[7] = (a[9] + a[16] + a[15] + a[5]);
sums[8] = (a[1] + a[13] + a[14] + a[5]);
sums[9] = (a[11] + a[17] + a[16] + a[7]);
sums[10] = (a[1] + a[12] + a[17] + a[9]);
sums[11] = (a[3] + a[14] + a[15] + a[7]);
sums[12] = (a[0] + a[12] + a[18] + a[15] + a[6]);
sums[13] = (a[2] + a[13] + a[18] + a[16] + a[8]);
sums[14] = (a[10] + a[17] + a[18] + a[14] + a[4]);
}
int test(void) {
int result, i;
fillfill();
fillsums();
for (i=0,result=1;i<15;i++) {
result = result && (!fill[i] || sums[i]==38);
}
return result;
}

void assign(int i) {
int j;


for (j=1;j<20;j++) {
if (tiles[j] == -1) {
a[i] = j;
tiles[j] = i;
if (test()) {
if (i==18) {
printf(" %2d %2d %2d\n", a[0],a[1],a[2]);
printf(" %2d %2d %2d %2d\n", a[11],a[12],a[13],a[3]);
printf("%2d %2d %2d %2d %2d\n", a[10],a[17],a[18],a[14],a[4]);
printf(" %2d %2d %2d %2d\n", a[9],a[16],a[15],a[5]);
printf(" %2d %2d %2d\n", a[8],a[7],a[6]);
exit(0);
}
assign(i+1);
a[i+1] = 0;
tiles[j] = -1;
} else {
a[i] = 0;
tiles[j] = -1;
}
}
}
}

int main(int argc, const char * argv[]) {
int i;

for (i=0;i<19;i++) {
a[i] = 0;
tiles[i+1] = -1;
}

assign(0);

return 0;
}

Anonymous said...

Brief note: in your list of a equations you list "b+e+i+m=38" twice. Not listed is "d+e+f+g=38". Obviously, error wasn't in your programming since you were able to solve.

bill.tubbs said...

Nice problem. I took this as an excuse to learn the Python SymPy package. Here is my code to produce the reduced set of equations using simp's solve function:


from sympy import symbols, solve
from sympy.parsing.sympy_parser import parse_expr

# Number of unknowns
n_unknowns = 19

variable_names = [chr(c + 97) for c in range(19)]

# Create SymPy variables
variables = symbols(variable_names)

print("\n{} unknowns:".format(len(variables)))
print(variables)

# These strings define the equations to be solved
hexagon_rows = [
'abc',
'defg',
'hijkl',
'mnop',
'qrs',
'cgl',
'bfkp',
'aejos',
'dinr',
'hmq',
'lps',
'gkor',
'cfjnq',
'beim',
'adh'
]

def make_expression(chars, rhs=0):
return parse_expr('+'.join(list(chars)) + '-' + str(rhs))

expressions = []
for chars in hexagon_rows:
expressions.append(make_expression(chars, 38))

print("\n{} equations to solve:".format(len(expressions)))

for expr in expressions:
print("{} = 0".format(expr))

# Try to solve the equations
# (They can't be solved but SymPy reduces them down)
reduced_expressions = solve(expressions)

print("\nReduced to {} equations:".format(len(reduced_expressions)))
for var, expr in reduced_expressions.items():
print("{} = {}".format(var, expr))


Output of above code:

19 unknowns:
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s]

15 equations to solve:
a + b + c - 38 = 0
d + e + f + g - 38 = 0
h + i + j + k + l - 38 = 0
m + n + o + p - 38 = 0
q + r + s - 38 = 0
c + g + l - 38 = 0
b + f + k + p - 38 = 0
a + e + j + o + s - 38 = 0
d + i + n + r - 38 = 0
h + m + q - 38 = 0
l + p + s - 38 = 0
g + k + o + r - 38 = 0
c + f + j + n + q - 38 = 0
b + e + i + m - 38 = 0
a + d + h - 38 = 0

Reduced to 12 equations:
j = b - n - o
k = e - n - o - p - r + 38
l = -p - s + 38
i = -b - e + n + o + p
c = e - n + s
f = -b - e + n + o + r
g = -e + n + p
q = -r - s + 38
m = -n - o - p + 38
h = n + o + p + r + s - 38
d = b + e - 2*n - o - p - r + 38
a = -b - e + n - s + 38

bill.tubbs said...

Here's my complete Python script which includes the script above to do the Gaussian elimination and then goes on to find the 12 solutions using permutations from itertools and numpy arrays. It takes about 2min 40s! https://github.com/billtubbs/aristotle