The 36 cube is a puzzle in which you fill a board with towers so that the top is flat and each column and row only has one member of each color: http://www.thinkfun.com/flash/36cube/index.html
The board can be thought of as a 6 by 6 matrix of numbers between 1 and 6 where the numbers represent the heights of the towers that must be placed in the board. We can represent the board as a list of python lists:
places = [
[6, 3, 2, 4, 5, 1],
[4, 5, 1, 6, 3, 2],
[1, 2, 4, 3, 6, 5],
[2, 5, 3, 6, 1, 4],
[3, 1, 5, 2, 4, 6],
[5, 4, 6, 1, 2, 3],
]
We have six colors, each with one tower of each size. We can represent this as a mapping between a simple string and a list of sizes left:
colors = {
"a": [1,2,3,4,5,6],
"b": [1,2,3,4,5,6],
"c": [1,2,3,4,5,6],
"d": [1,2,3,4,5,6],
"e": [1,2,3,4,5,6],
"f": [1,2,3,4,5,6],
}
If there is a solution, each row of the board will have a permutation of ["a", "b", "c", "d", "e", "f"]. That is to say, one tower of each color (which letter represents which color doesn't matter).
We can use itertools.permutations to get the choices for the color ordering for each row.
>>> from itertools import permutations
>>> six_choices = permutations(["a", "b", "c", "d", "e", "f"])
>>> six_choices
<itertools.permutations object at 0x10331a410>
>>> list(six_choices)
[('a', 'b', 'c', 'd', 'e', 'f'),
('a', 'b', 'c', 'd', 'f', 'e'),
('a', 'b', 'c', 'e', 'd', 'f'),
('a', 'b', 'c', 'e', 'f', 'd'),
...
('f', 'e', 'd', 'a', 'b', 'c'),
('f', 'e', 'd', 'a', 'c', 'b'),
('f', 'e', 'd', 'b', 'a', 'c'),
('f', 'e', 'd', 'b', 'c', 'a'),
('f', 'e', 'd', 'c', 'a', 'b'),
('f', 'e', 'd', 'c', 'b', 'a')]
There are 6! = 6x5x4x3x2x1 = 720 ways that the colors can be ordered in a row. Since the mapping of our strings to the six colors is arbitrary, we can simply say that ["a", "b", "c", "d", "e", "f"] is the first row of our solution(s). We're a sixth of the way there! In fact, we can go ahead and rule out any of the choices for a row which have "a" in the 0th position, "b" in the 1st position "c" in the 2nd position and so on. How can we reduce the list of permutations above?
Let's create a couple of utility functions. Getting the row of a matrix which is expressed like our places matrix above is easy, just index the list, places[0] == [6, 3, 2, 4, 5, 1]. A little utility function to get the values of a column is in order:
def col(mat, num):
"""Given a matrix, `mat`, and a column number, `num`, return the values of the column"""
return [l[num] for l in mat]
Now, we can take out all of the choices that would cause a duplicate color to be inserted in a column.
def reduce_choices(choices, mat):
"""
`choices` is the list of possible valid choices for a row
`mat` is the given prospective solution
returns `new_choices`, a list of color row permutations not conflicting with the existing `mat`.
""""
new_choices = []
for choice in choices:
if not any([choice[i] in col(mat, i) for i in range(6)]):
new_choices.append(choice)
return new_choices
Now we can generate all of the possible matrices that use each of our colors exactly 6 times and with exactly 1 instance of each color for every row and column. The algorithm is ugly and slightly less than pythonic but pretty simple. Start with the first row filled. Reduce the choices for the second row so that none of the columns conflict. Try the first one. Reduce the choices for the 3rd row so that they don't conflict with the new prospective matrix. And so on, should be pretty simple to see.
def get_prospects():
prospect_solution = [("a", "b", "c", "d", "e", "f")]
five_choices = reduce_choices(six_choices, prospect_solution)
for choice5 in five_choices:
prospect_solution.append(choice5)
four_choices = reduce_choices(five_choices, prospect_solution)
for choice4 in four_choices:
prospect_solution.append(choice4)
three_choices = reduce_choices(four_choices, prospect_solution)
for choice3 in three_choices:
prospect_solution.append(choice3)
two_choices = reduce_choices(three_choices, prospect_solution)
for choice2 in two_choices:
prospect_solution.append(choice2)
one_choices = reduce_choices(two_choices, prospect_solution)
for choice1 in one_choices:
prospect_solution.append(choice1)
yield prospect_solution
prospect_solution.pop()
prospect_solution.pop()
prospect_solution.pop()
prospect_solution.pop()
prospect_solution.pop()
prospect_solution.pop()
Let's look at a few of the matrices that we can generate with get_prospects.
>>> it = get_prospects()
>>> it.next()
[('a', 'b', 'c', 'd', 'e', 'f'),
('b', 'a', 'd', 'c', 'f', 'e'),
('c', 'd', 'e', 'f', 'a', 'b'),
('d', 'c', 'f', 'e', 'b', 'a'),
('e', 'f', 'a', 'b', 'c', 'd'),
('f', 'e', 'b', 'a', 'd', 'c')]
>>> it.next()
[(a', 'b', 'c', 'd', 'e', 'f'),
('b', 'a', 'd', 'c', 'f', 'e'),
('c', 'd', 'e', 'f', 'a', 'b'),
('d', 'c', 'f', 'e', 'b', 'a'),
('e', 'f', 'a', 'b', 'd', 'c'),
('f', 'e', 'b', 'a', 'c', 'd')]
>>> it.next()
[('a', 'b', 'c', 'd', 'e', 'f'),
('b', 'a', 'd', 'c', 'f', 'e'),
('c', 'd', 'e', 'f', 'a', 'b'),
('d', 'c', 'f', 'e', 'b', 'a'),
('e', 'f', 'b', 'a', 'c', 'd'),
('f', 'e', 'a', 'b', 'd', 'c')]
These are 3 different ways to lay out the colors so that every column and row has every color exactly once. However, see that from the bottom left to the top right, we have all color "f". Looking back on the places matrix, we see that that diagonal has 3 3s, 2 1s and a 5. The "f" color has towers of height (1, 2, 3, 4, 5, 6), not (3, 3, 3, 1, 1, 5). So, these prospects are not solutions. Can we really just grind out every prospect and check to see if each is a solution? Actually, yes. It turns out that rendering all of the prospective matrices using the above get_prospects algorithm returns a modest 1,128,960 prospects.
Here is one way to check to see if a prospective color arrangement matrix is a solution (where each height tower of each color is used exactly once).
def issolved(matrix):
colorz = copy.deepcopy(colors)
for row in range(6):
for col in range(6):
color = matrix[row][col]
height = places[row][col]
try:
colorz[color].remove(height)
except ValueError:
return False
return True
If we can iterate through each value of i and j, each place in our places board, popping towers out of our color mapping without trying to remove the same tower twice, the prospective matrix is a solution. Alright, cross your fingers!
def go():
for mat in get_prospects():
if issolved(mat):
pprint(mat) # or do something else ...
Okay, so, we can just run this thing and print the solutions:
if __name__ == "__main__":
go()
So, that gives us:
[('a', 'b', 'c', 'd', 'e', 'f'),
('b', 'c', 'e', 'f', 'a', 'd'),
('c', 'a', 'f', 'e', 'd', 'b'),
('e', 'f', 'd', 'c', 'b', 'a'),
('f', 'd', 'a', 'b', 'c', 'e'),
('d', 'e', 'b', 'a', 'f', 'c')]
[('a', 'b', 'c', 'd', 'e', 'f'),
('b', 'f', 'e', 'c', 'a', 'd'),
('c', 'a', 'f', 'e', 'd', 'b'),
('e', 'c', 'd', 'f', 'b', 'a'),
('f', 'd', 'a', 'b', 'c', 'e'),
('d', 'e', 'b', 'a', 'f', 'c')]
[('a', 'b', 'c', 'd', 'e', 'f'),
('e', 'c', 'b', 'f', 'd', 'a'),
('c', 'e', 'f', 'a', 'b', 'd'),
('d', 'f', 'e', 'c', 'a', 'b'),
('f', 'd', 'a', 'b', 'c', 'e'),
('b', 'a', 'd', 'e', 'f', 'c')]
[('a', 'b', 'c', 'd', 'e', 'f'),
('e', 'f', 'b', 'c', 'd', 'a'),
('c', 'e', 'f', 'a', 'b', 'd'),
('d', 'c', 'e', 'f', 'a', 'b'),
('f', 'd', 'a', 'b', 'c', 'e'),
('b', 'a', 'd', 'e', 'f', 'c')]
The four unique solutions to the 36 cube.
Interesting, the inventor comments here that "Yes, I took some pleasure in the fact that the puzzle couldn’t be solved by computer alone." The inventor and the author of the post discuss some twists to the puzzle involving it being easy to get to 34 out of 36 correct but 2 of the colors have some special stipulations, "The assumption that all towers of the same size only differ in color is wrong." and "The two special towers are the orange one of height 5 and the red one of height 6."
Hrm .. I think this solution is by computer alone without any special knowledge of these twists since I don't really know what they are talking about!
You can get the full script here: https://s3.amazonaws.com/skyl/final_puzzle.py
