Automatic Puzzle Solver

The challenge of puzzle solving is a subject that has occupied the scientific community working on computer vision for decades. Indeed, this ‘problem’, and the methods used to solve it, are often presented as the first step of a possible extension towards more serious subjects, such as the reconstruction of archaeological artifacts for example. It is a more playful approach that is at the origin of this project. Seeing the possibility of using computer vision to help with puzzle solving, this project proposes to develop an ‘automatic’ puzzle solving method, in real-time, observing the pieces with the user and indicating where to place them.

This project therefore implements numerous image analysis tools and seeks a certain form of robustness necessary due to its real-time operation. Our method proposes to function iteratively in real-time, allowing us to accompany the user in solving the puzzle. This approach, combined with better feature detection, allows for more robust puzzle resolution with a larger number of pieces, surpassing all benchmarks.

The overall puzzle solver pipeline is as follows:

1. A phone, attached to a stand, allows real-time observation of a certain number of pieces (about 10 to 15) on a white background. This phone is connected to the computer through an application to retrieve the camera feed. Additionally, the global image of the puzzle (on the box) is given as input.

2. An image is taken by the camera at a given regular interval and processed by the algorithm.

3. On the computer screen, an interface displays the phone’s video, as well as the puzzle under construction, indicating each time which piece to move and its location on the final puzzle.

All implementation details: morphological operations, feature detection and matching, homographies, verification after piece selection, are in the attached paper.

Associated Repository