A Computer Solution of Polygonal Jigsaw-Puzzles

DAIMI Report Series

View Publication Info
Field Value
Title A Computer Solution of Polygonal Jigsaw-Puzzles
Creator Lynning, Ejvind
Description 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.
Publisher Aarhus University
Date 1973-02-01
Type info:eu-repo/semantics/article
Peer-reviewed Article
Format application/pdf
Identifier http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6424
Source DAIMI Report Series; No 9 (1973): PB-9 A Computer Solution of Polygonal Jigsaw-Puzzles
DAIMI Report Series; No 9 (1973): PB-9 A Computer Solution of Polygonal Jigsaw-Puzzles
Language eng
Relation http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6424/5548

Contact Us

The PKP Index is an initiative of the Public Knowledge Project.

For PKP Publishing Services please use the PKP|PS contact form.

For support with PKP software we encourage users to consult our wiki for documentation and search our support forums.

For any other correspondence feel free to contact us using the PKP contact form.

Find Us


Copyright © 2015-2018 Simon Fraser University Library