Solving Sudoku Puzzles from Images with Deep Learning

Sudoku is a popular number placement puzzle that has fascinated millions of people around the world. In classic Sudoku, the objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids contains all of the digits from 1 to 9, with no repeats. The puzzle provides an initial partially completed grid, and the challenge is to use logic to fill in the missing digits.

While Sudoku is a fun and addictive game for humans, it also presents an interesting challenge for artificial intelligence. In particular, solving Sudoku puzzles from images of them, rather than from a digital representation of the initial grid, requires the integration of computer vision and deep learning techniques. In this post, we‘ll walk through how to build a Sudoku solving system that takes an image as input, extracts the Sudoku grid, classifies the digits in each cell using a deep learning model, and then finds the solution using a backtracking algorithm. We‘ll use Python and popular libraries like OpenCV and TensorFlow.

Here are the key steps in the process:

1. Digit Classification Model

The first step is to build a deep learning model that can classify the digits 0-9 (as well as a class for empty cells) from small images. We‘ll train this model on the Chars74K dataset, which contains over 74,000 images of digits and characters that we can use for our purposes.

To build the model, we‘ll use a convolutional neural network (CNN) architecture. CNNs have been very successful at image classification tasks because of their ability to automatically learn visual features at different scales. A basic CNN consists of alternating convolutional layers and pooling layers, followed by one or more fully connected layers. The convolutional layers apply learned filters to the input image to detect features, while pooling layers downsample the outputs to reduce dimensionality. We‘ll use a simple architecture with 2-3 convolutional and pooling layers, followed by 1-2 dense layers with dropout regularization.

Before training, we‘ll preprocess the input images to make them more consistent and reduce noise. This includes resizing to a standard 32×32 size, converting to grayscale and normalizing pixel values. We‘ll also use data augmentation – applying random transforms to the training images like small rotations, shifts, shears and zooms – to improve the robustness of the model.

Training the model is done by iteratively passing batches of images through the network, comparing the predicted classes to the actual labels, and adjusting the model weights to minimize the categorical cross entropy loss. We‘ll use an optimizer like RMSprop and train for 10-20 epochs. After training, we‘ll evaluate the final model accuracy on a held-out test dataset.

2. Sudoku Grid Extraction

Once we have a trained digit classifier, the next step is to extract the Sudoku puzzle grid from an input image. We start by assuming the image contains only the puzzle, with no extra borders or markings.

The key substeps are:

1. Preprocess the image by resizing to a standard size, converting to grayscale and applying adaptive thresholding. This helps isolate the grid lines.
2. Find all contours (curves joining continuous points of the same color) in the thresholded image.
3. Select the largest contour by area, which should correspond to the outer border of the puzzle grid.
4. Perform a perspective transform using the corner points of the largest contour. This rectifies the grid to a square with known dimensions, removing any rotation or skew.
5. Split the rectified grid into 81 equal-sized cells using array slicing.

We now have a set of 81 images corresponding to each cell of the original Sudoku grid. We can pass each of these to our trained digit classification model.

3. Digit Classification

To classify the digits, we‘ll preprocess each cell image the same way as we did for the training data – resize to 32×32, grayscale, and normalize. Then we simply pass the image through the trained CNN model and take the highest probability class as the prediction.

There are a few potential issues to watch out for:

• Some cells will be empty, but the classifier only is trained on digits. We can either modify the model to have an "empty" class, or just take the digit class with the highest predicted probability and set a threshold below which we consider it empty.
• The extracted cells might have noise or not be perfectly centered on the digit. Data augmentation during training helps here, but we might still misclassify some digits.
• Overlapping digits from adjacent cells can cause problems if the extraction isn‘t perfect. Again, having an empty class in the model can help.

After classifying all 81 cells, we‘ll have the initial state of the Sudoku board, ready to be solved. We‘ll represent this as a 9×9 matrix, with 0s for the empty cells.

4. Solving the Sudoku Puzzle

Finally, we can apply a classic algorithm to solve the Sudoku, given the initial cell values. We‘ll use a recursive backtracking approach:

1. Find an empty cell (if there are none, the puzzle is solved)
2. Try each digit from 1-9 in the cell
3. Check if the digit conflicts with any in its row, column or 3×3 block
4. If there is a conflict, backtrack and try the next digit
5. If no conflicts, place the digit and recursively try to fill the next empty cell
6. If this recursive call returns a valid solution, great, otherwise backtrack and try the next digit
7. If no digit works in the current cell, return False to indicate the previous digits placed can‘t lead to a solution

This depth-first search will efficiently explore the space of possible solutions, backtracking when it hits an invalid state. In the worst case, it will check all possible placements which is very large, but in practice it can find a solution very quickly by eliminating invalid states early.

Once we have the solution matrix, we‘re done! We could format it into an output image to visualize the result if desired.

Putting It All Together

Let‘s walk through a complete example, solving a Sudoku puzzle from an image:

[Insert example input image]

First, we load the trained digit classification model and the input puzzle image. We localize the puzzle grid in the image using the contour and perspective transform method:

[Code snippet for grid extraction] [Intermediate image of extracted and rectified grid]

Next, we split the grid into individual cells and classify the digits in each cell:

[Code snippet for cell extraction and classification] [Visualization of model predictions on each cell]

We arrange the predictions in a 9×9 matrix, representing the initial puzzle state:

[Code snippet to create matrix] [Output of initial matrix]

Finally, we pass this matrix into our recursive solver:

[Code snippet of solver]

And in a matter of milliseconds, it returns the solution:

[Output of solution matrix] [Visualization of solution numbers overlaid on original image]

Incredible! With just an input image, we were able to automatically solve the Sudoku puzzle by integrating computer vision and deep learning. The full code for this project is available on GitHub [link to repo].

Future Work

There are a number of ways this system could be improved and extended:

• Use a larger and more diverse dataset for digit classification, to improve accuracy on puzzle images in the wild
• Train an object detection model (like YOLO or SSD) to automatically localize the puzzle grid in complex images
• Experiment with different CNN architectures and hyperparameters
• Optimize the backtracking solver with more advanced heuristics or even machine learning to guide the search
• Deploy the trained models in a mobile app that can solve puzzles from a phone camera in real-time
• Generalize to Sudoku variations like Mini Sudoku, Wordoku, Killer Sudoku by training on labeled examples
• Integrate with a robotic arm to automatically write the solved digits onto a printed puzzle!

I hope this post gave you a sense of how deep learning can be applied to the classic problem of solving Sudoku puzzles. Computer vision and neural networks open up a world of possibilities for building intelligent systems that interact with the visual world. What will you build next?