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
 
Contributor
 
Date 1973-02-01
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
Peer-reviewed Article
 
Format application/pdf
 
Identifier http://ojs.statsbiblioteket.dk/index.php/daimipb/article/view/6424
10.7146/dpb.v2i9.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
2245-9316
0105-8517
 
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

Twitter

Copyright © 2015-2018 Simon Fraser University Library