A HEURISTIC APPROACH TO SOLUTION OF CHECKERBOARD PUZZLES,
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1964
- Accession Number
- AD0609570
Entities
People
- Gilbert J. Hansen