Automated solutions to incomplete jigsaw puzzles

摘要

The jigsaw puzzle re-assembly problem has been investigated only intermittently in the research literature. One potential theoretical line of research concerns jigsaw puzzles that do not have a complete set of puzzle pieces. These incomplete puzzles represent a difficult aspect of this problem that is outlined but can not be resolved in the current research. The computational experiments conducted in this paper demonstrate that the proposed re-assembly algorithm being optimised to re-assemble the complete jigsaw puzzles is not efficient when applied to the puzzles with missing pieces. Further work was undertaken to modify the proposed algorithm to enable efficient re-assembly of incomplete jigsaw puzzles. Consequently, a heuristic strategy, termed Empty Slot Prediction, was developed to support the proposed algorithm, and proved successful when applied to certain sub-classes of this problem. The results obtained indicate that no one algorithm can be used to solve the multitude of possible scenarios involved in the re-assembly of incomplete jigsaw puzzles. Other variations of the jigsaw puzzle problem that still remain unsolved are presented as avenues for future research.