A Heuristic Approach to Solution of Checkerboard Puzzles

摘要

The problem of reconstructing a checkerboard cut into a number of straight edge pieces was solved by a digital computer program employing a varity of heuristics. The major heuristics used were considerations of the symmetry of the pieces, correct color combinations, optimal selection of the place on the board to fit the next piece, the optimal piece to select at each stage in fitting the puzzle together, pairing of the pieces, and selecting the first piece to be used in starting the puzzle. These heuristics were applied in order to simulate as closely as possible the way in which a human being would proceed in obtaining a solution. These enabled us to minimize the number of tries necessary to obtain a solution, thus making the solution time reasonable. Two 8x8 checkerboard puzzles were tried. The first consisted of 12 pieces and was solved in 8 minutes. The second had 13 pieces and took 1 hour and 25 minutes. The recursive program was written in IPL-V and run on the Univac 1107 computer. (Author)