Comprehensive survey of the solving puzzle problems


Yılmaz S., Nabıyev V.

COMPUTER SCIENCE REVIEW, vol.1, 2023 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Review
  • Volume: 1
  • Publication Date: 2023
  • Doi Number: 10.1016/j.cosrev.2023.100586
  • Journal Name: COMPUTER SCIENCE REVIEW
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Compendex, INSPEC, zbMATH
  • Keywords: Computer-aided reconstruction, Dissection puzzles, Fragments assembly, Puzzle problems, Reconstruction of the fragmented objects, Solving real-world jigsaw puzzle
  • Karadeniz Technical University Affiliated: Yes

Abstract

Solving puzzle problems using computer-aided methods is becoming more common with applications in forensic science, restoration, banking system, and multimedia. However, only a few surveys have been published on this topic, the most recent being more than a decade old. The scope of 2D puzzle problems is extensive, and the number of computer-aided methods has increased in recent years. In this paper, we have presented a comprehensive survey to pave a roadmap for researchers dealing with puzzle problems. This study classifies 2D puzzle problems in a novel way, considering many examples such as dissection, combinatorial and double-sided puzzles and reclassifies computer-aided methods to cover the studies carried out in recent years. Various strategies (pre-grouping and global consistency approach) have been investigated to solve the puzzle problem effectively. The computer-aided methods have been examined deeply, including many recent methods related to squared jigsaw puzzles, torn photographs, banknotes, and fragmented documents, and they are compared to each other. In addition, new topics such as combining mosaic pieces and Islamic architectural motif puzzle problems have been proposed to the interest of researchers. In conclusion, our study shows many research opportunities that are not yet solved by any computer-aided method. (c) 2023 Elsevier Inc. All rights reserved.