"A Modern Treatment of the 15 Puzzle." Amer. The maximum number of moves required to solve the generalization of the 15 puzzle for, 2. The 36-move solution given by Dudeney (1949). (OEISĪ046164), giving 634 solutions better than Number of distinct solutions in 28, 30, 32. The best solution requires 30 moves (Gardner 1984, pp. 200 and 206-207). Reversing the order of the "8 Puzzle" made on a board can be proved to require at least 26 moves, although On whether the graph is bipartite (Archer 1999). Nodes, with the exception of cycle graphs and the theta0 graph,Įither exactly half or all of the possible labelings are obtainable by sliding labels, depending A more general result due to Wilson (1974) showed that for any connected "no really easy proof seems to be known," Archer (1999) presented a simple Despite the assertion of Herstein and Kaplansky (1978) that While odd permutations of the puzzle are impossible to solve (Johnson 1879), all even permutations are Since this number is odd, the above arrangement of the puzzle cannot be solved. Similarly, in the above random arrangement of squares, the inversion counts are 12, 9, 9, 5, 4, 4, 3, 3, 0, 3, 3, 2, 1, 1, and 0, giving an inversion sum of 59. In other words, if the permutation symbol of the list is, the position is possible, whereas if the signature is, it is not. Is even, the position is possible, otherwise it is Also define to be the row number of the empty square. Stated more simply, is the number of permutation Where the sum need run only from 2 to 15 rather than 1 to 15 since there are no numbers less than 1 (so If the square containing the number appears "before" (reading the squares in the boxįrom left to right and top to bottom) numbers that are less than, then call it an inversion of order, and denote it. To address the solubility of a given initial arrangement, proceed as follows. Some initial arrangements, this rearrangement is possible, but for others, it is The goal is to reposition the squares from a given arbitrary startingĪrrangement by sliding them one at a time into the configuration shown above. The 15 puzzle consists of 15 squares numbered from 1 to 15 that are placed in a box leaving one position out The actual inventor was Noyes Chapman, the Postmaster of Canastota, New York, and he applied for a patent in March 1880. Loyd first claimed in 1891 that he invented the puzzle, and he continued until his death a 20 year campaign to falsely take credit for the puzzle. The puzzle craze that was created by the 15 puzzle began in January 1880 in the United States and in April in Europe and ended by July 1880. However, research by Slocum and Sonneveld (2006) has revealed that Sam Loyd did not invent the 15 puzzle and had nothing to do with promoting or popularizing it. The "15 puzzle" is a sliding square puzzle commonly (but incorrectly) attributed to Sam Loyd.
0 Comments
Leave a Reply. |