My daughters recently received a 36 Cube puzzle from Thinkfun for Christmas.  This puzzle contains a 6x6 grid of pegs, each one of 6 possible sizes, each size appearing 6 times.  The puzzle uses a collection of 36 pieces that fit onto the pegs, composed of all possible combinations of 6 sizes and 6 colors.  Each puzzle piece can only be put on a peg of the corresponding size.   The goal is to find a configuration in which each row and column of the puzzle grid contains each of the 6 possible colors.  Thus no color can appear twice in any row or column.

I wrote a computer program which I hoped would find a solution to the puzzle.  Instead, it demonstrates that this puzzle cannot be solved.  The program tries to build a solution by examining each location of the 6x6 grid in turn.  At each grid location the program considers all possible unused pieces of the correct size that do not duplicate a color already present in the current row and column.   For each such "legal" piece, the program moves the piece into the grid and proceeds to the next grid location.  This process continues until a successful solution is found or no legal moves can be made from any of the partial solutions considered. 

One can think of the algorithm as exploring the "search tree" of all possible configurations.  The root of the tree is the empty configuration in which no pieces are yet placed on the grid.  Stemming from this root node are 6 branches,  corresponding to the 6 different pieces that can be placed at the first location.   Assuming that the next grid position we consider is adjacent to the original location, there will be 5 branches stemming from each of the nodes at level one, corresponding to the legal moves that can continue the first move.  This is because one of the 6 matching pieces will duplicate the color already played at the parent level.   If we continue in this manner then each configuation at the nth level of the tree has n pieces placed on the grid (we call the level of the root the 0th level).    The algorithm searches all possible configurations, stopping the construction (the exploration of the tree beneath the current node)  only when no possible continuations are possible.

While such a brute-force algorithm might seem infeasible, it turns out to be easy to implement in a few seconds of computing time.  This is because most branches are terminated relatively early in their construction.    Here is the c program that demonstrates that no solution can be found for this puzzle: puzzle36.c    The program is written in c and can be compiled and run on any computer.  The program takes an argument from the command line which is a number from 1 to 36, giving the number of consecutive grid locations the algorithm must search.  When given n as the input,  the program will stop once it finds a legal configuration on the first n grid locations and print out the solution.    The program quickly finds solutions for any number from 1 to 34, but fails for 35 and 36.  Here is sample output for the program.  

Is this a proof that the puzzle is impossible?   For this to be a convincing argument, one must examine the program to see that it really does generate every possible configuration, ending a particular construction only when it can no longer be continued.  Luckily the program is quite simple, so it is relatively easy to verify that the program performs as claimed.  I believe that most programmers familiar with recursion will be able to verify that the program is correct.

I am interested in the responses of others who have worked on this puzzle and hope you will add your comments here:

You are invited to read other readers' comments here.  Your comments will be automatically included.

Prof. Christopher Raphael