A Computer Solution of Polygonal Jigsaw-Puzzles

  • Ejvind Lynning

Abstract

This paper describes a program to solve any jigsaw-puzzle involving pieces of polygonal shape. An efficient solution has been found to depend on a number of ad hoc strategies which are described in detail in the paper. The puzzles are solved by successively placing individual pieces in the region to be covered using a depth-first tree search algorithm. A formal representation of regions, pieces, and placings of pieces is defined. The main idea behind the chosen representation is to orient clockwise the Dolygons making up a region, and to orient counterclockwise the pieces to be placed. Placing a piece means computing a valid new region, i. e., one or more clockwise oriented polygons, constructed from the previous one by removing the part corresponding to the piece which is placed. The data structure and the procedures required to examine where pieces can be placed and to perform the placings are also described. All the puzzles that have so far been presented to the program have been successfully solved in a resonable time.

Author Biography

Ejvind Lynning
Published
1973-02-01
How to Cite
Lynning, E. (1973). A Computer Solution of Polygonal Jigsaw-Puzzles. DAIMI Report Series, 2(9). https://doi.org/10.7146/dpb.v2i9.6424