¹ The game of chess is rich in examples that can be constructed from it. For example, an other interesting challenging puzzle is the knight's tour, where one starts by positioning the knight on one square of an N by M chessboard and, using only legal knight moves, tries for the knight to visit all squares exactly once. Hurd and Truatman [HURD93] have shown that this problem was surprisingly related to the 15-puzzle where one slides 15 blocks in a 4 by 4 array trying to reconstruct a given pattern.