A Criterion-based Genetic Algorithm Solution to the Jigsaw Puzzle NP-Complete Problem

The foremost objective of the present research project consists developing an Intelligent Robotic System (SIR for its name in Spanish, Sistema Inteligente Robotico) that solves an unknown jigsaw puzzle in a reduced amount of time. To fulfill the objective, SIR applies pattern recognition techniques as edge and feature detection in conjunction with Genetic Algorithms. Many authors have addressed the jigsaw puzzle problem. By comparing their work, the NP-Complete nature of the problem appeared as a common denominator on them. SIR relies on those experiences, results, conclusions and observations as a working base for a new approach to the problem. This approach involves a conversion of the puzzle model to a Graph Theory model. The study of this model plus the inclusion of a different analogy and solution approach is the main contribution of this work. It describes the theoretical and practical frameworks, current state of the project and future work.