each colour appears exactly once on each of the 4 sides of the stack is NP-complete. The cube stacking game is a two-player game version of this puzzle. Given an ordered list of cubes, the players take turns adding the next cube to the top of a growing stack of cubes. The loser is the first player to add a cube that causes one of the four sides of the stack to have a color repeated more than once. Robertson and Munro proved that this game is PSPACE-complete, which illustrates the observation that NP-complete puzzles tend to lead to PSPACE-complete games. References Computational problems in graph theory Combination puzzles NP-complete problems