# UnPuzzled

# What is UnPuzzled ?

It is 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.

# Unpuzzling

Here’s an animation of the solver in action

# GitHub repository

The code for this project can be found at https://github.com/nivbhaskhar/UnPuzzled

Additionally, the code to deploy a Gradio based web application on Heroku, which simulates the puzzle-solving by the solver, can also be found in the same repository.

# Results

I evaluated solvers based on three checking-adjacency models, namely *AdjacencyClassifier_NoML* (a hand-engineered model), *FromScratch* (a simple CNN) and *ResNetFT* (a fine-tuned ResNet 18 model).

There were 67 *six-by-six* puzzles, 11 *five-by-five* puzzles and 2 *four-by-four* puzzles in the evaluation set

puzzle_sizes | no_of_puzzles | |
---|---|---|

0 | 36 | 67 |

1 | 25 | 11 |

2 | 16 | 2 |

Both the *AdjacencyClassifier_NoML* and the *ResNetFT* solved 87.5 % of the puzzles completely correctly. *FromScratch* underperformed by solving only 37.5 % of the puzzles completely correctly.

AdjacencyClassifier_NoML | FromScratch | ResNetFT | |
---|---|---|---|

avg_time_taken (sec) | 11.2126 | 18.9795 | 23.0482 |

percentage_solved | 0.875 | 0.375 | 0.875 |

avg_puzzle_sizes | 33.9875 | 33.9875 | 33.9875 |

# A venn diagram to visualize the comparisons

# Comments

I further visually investigated what the models did on puzzles they did not solve completely correctly. It turned out that the solvers were putting together several chunks of the puzzles correctly even if they were not placing the pieces in the correct positions in the puzzle board. Further, the solvers sometimes put back mostly correct but rotated versions of the images. The current evaluation classified all these puzzles as *unsolved*.

If there are several similar pieces, and a solver chose and fit an incorrect piece, the puzzle of course will not be completely correctly solved. However the solver might (and did often) recover and get local chunks of the puzzle right. Perhaps a non-binary evaluation metric would aid in gauging the efficacy of these puzzle-solvers.