UnPuzzled

A Jigsaw puzzle solver using AI

An overview

This project consists of two components : creation and solving of puzzles and checking adjacency of puzzle pieces.

I construct a puzzle generator, which takes a given image and cuts it up into a rectangular grid of uniform square puzzle pieces with each puzzle piece being of a specified dimension. It further randomly rotates each square piece by 0/90/180/270 degrees counterclockwise and shuffles up the pieces, thus creating a puzzle.

I construct several models (machine-learning based and non-machine learning based) which are trained to detect if two given puzzle pieces are adjacent or not. I create custom datasets for these models using a puzzle-pieces-pair generator which is similar to the puzzle generator mentioned above. The actual images to construct the custom datasets are taken from the CUB-200 dataset. From the start, I split the images in the CUB-200 dataset into training, validation and test portions. I construct custom validation and test datasets to validate and evaluate the checking-adjacency models.

I design a search algorithm which takes a puzzle board with the top-left corner filled in, searches for the best pieces to fit into the board till the board is filled completely. The task of determining which pieces fit better makes use of the checking-adjacency models. I create solvers, which integrate the models with the search algorithm. Finally, I evaluate and compare the performances of the solvers on a test-data set of puzzles which are constructed by the puzzle generator from the test-portion of the CUB-200 dataset split.

I also give the code for a web-application built using Gradio which simulates the puzzle-solving by the solver which can be deployed on Heroku

---

The following notebooks contain code and more precise notes for each step of this project. If the jupyter notebooks take too long to load, please open the markdown versions, which load faster.

Contents

Checking adjacency: A subproblem

1. Problem definition, data generation and visualization

   • Notebook, Markdown

2. Adjacency distance: A no ML approach

   • Notebook, Markdown

3. Model architectures

   • FromScratch : A CNN model

     • Notebook, Markdown

   • ResNetFT : Finetuning the ResNet18 model

     • Notebook, Markdown

4. Training

   • Training template

     • Notebook, Markdown

   • Training FromScratch

     • Notebook, Markdown

   • Training ResNetFT

     • Notebook, Markdown

5. Evaluation and comparisons of models

   • Notebook, Markdown

---

Puzzle solver: A search

1. Puzzle generator

   • Notebook, Markdown

2. Search template

   • Notebook, Markdown

3. Solvers

   • In action

     • Notebook, Markdown

   • A step by step display

     • Notebook, Markdown

4. Evaluation and comparisons of solvers

   • Notebook, Markdown

5. Analysis of incorrectly solved puzzles

   • Notebook, Markdown

---

Unpuzzler: An application

1. Web application code
   • Notebook, Markdown