The 36 Cube is a puzzle designed by Derrick Niederman and manufactured by ThinkFun. It consists of a base with a 6×6 array of pedestals of different heights. There are also 36 hollow rods that fit onto these pedestals. There are six colours of rods, and of each colour there are 6 rods of different lengths. The aim is to place the rods on the base so that they all reach the same height, and that each row and each column contains rods of all six colours.

There are 6 pieces of each height, so there are 6! ways to arrange the pieces
of a particular height on the corresponding pedestals on the base. This leads to a total
of 6!^{6} = 139,314,069,504,000,000 ways of arranging all the pieces so they
all reach the same height. As with all matching puzzles this number is not a good
representation of the puzzle's difficulty, since you would rarely continue placing
pieces after you already have two of the same colour in a row or column.

Daniel Hepper's blog has a set of hints, the solution, and a computer program (python) to solve it.

The basis of this puzzle is the concept of a Graeco-Latin Square. The elements in the
square have two properties, and each property has n possible values (e.g. six different heights
or colours). The pieces are all unique, any every pair of property values occurs exactly
once. If these n^{2} pieces are arranged in a square such no row or column contains
two pieces which match in one of the properties (e.g. same colour, or same height) then you
have a Graeco-Latin square.

For example, using a deck of playing cards you can arrange the court cards and aces in a 4×4 square so that each row/column contains all four values and all four suits.

JS | QH | KC | AD |

AH | KS | QD | JC |

QC | JD | AS | KH |

KD | AC | JH | QS |

This 4×4 square is essentially unique, because all other order 4 Graeco-Latin squares can be derived from it by permuting the rows or columns, and permuting the colours or values.

Unfortunately it turns out that no order 6 Graeco-Latin square exists. It is not possible to arrange the pieces of the 36 Cube so that there is no row or column with two rods of the same colour or height. Nevertheless it is possible to solve this puzzle with a sneaky trick. You cannot cheat with the colours, but it is possible to cheat with the rod lengths. There are two pedestals on the base and two rods which have subtly different shapes. This allows one rod of length 6 to fit completely over a base pedestal of length 1, and one rod of length 5 to fit onto the tip of a pedestal of length 0. Therefore if these two special rods are on these two special positions, they can be swapped without changing their total heights.

On my puzzle the two special rods are the orange rod of length 6 and the yellow rod of length 5. The colours may be different on your puzzle (some use orange and red). These two pieces have a slightly different structure on the inside than all the other pieces of those lengths. The two special pedestals for these pieces are surrounded by taller pedestals so as not to be too obvious. When the puzzle is solved it is almost impossible to see that there are rows or columns containing two rods of the same length.

Here are two solutions, from which all others can be derived. The base is oriented such that the tallest corner pedestal is at the bottom right. The two special pieces/pedestals, indicated in the drawing by a red border, lie in the third column, second and fourth row.

By swapping the yellow rods of lengths 1 to 4 with the orange ones you get two more solutions.

On all of these you can permute the four colours other than yellow and orange (the two colours that have the special pieces). This results in a total of 24·4 = 96 solutions.