# Sudoku Solver using Image Processing and Neural Networks

Can Neural Networks and Image Processing be able to solve sudoku puzzles?

I love solving sudoku puzzles. After reading articles in the local newspaper, I’m solving the sudoku and crossword puzzle. It is a good brain exercise to start the morning. After learning some lessons on image processing, I just thought, can I use what I learned to automatically solve these from scanned images? My teammates and I came up with a simple algorithm to solve this. Many thanks to Tal, Lyon, and Aids for helping me creating this.

**Overall Process**

The process of making this are the following:

- Binarization of Images
- Extracting Data using Connected Components
- Apply Convolutional Neural Network to predict the digits.
- Apply py-sudoku in solving the puzzle.

In my previous post, we were able to perform binarization and extracting data from images. You may visit this post for more details about the first two steps. https://kdtabongds.medium.com/extracting-data-from-photos-using-image-processing-techniques-4b0f665825d1.

The code below is tailor-fit for a sudoku puzzle.

import matplotlib.pyplot as plt

import numpy as np

import pandas as pdfrom skimage.io import imread, imshow

from skimage.measure import label, regionprops, regionprops_table

from skimage.color import rgb2gray

from skimage.transform import resizesudoku_image = imread('sudoku.png')

sudoku_image = resize(sudoku_image, (900, 900), anti_aliasing=True)

def bounding_box(image):

"""

Returns an image with the corresponding bounding box plotted.

"""

#Binarization

bin_image = rgb2gray(image) > 0.3

label_im = label(bin_image, background=1)

#Region Props

regions = regionprops(label_im)

fig, ax = plt.subplots(figsize=(5,5))

count = 0

for props in regions:

minr, minc, maxr, maxc = props.bbox

area = (maxr - minr)*(maxc - minc)

#Filtering Box by Area

if area > 500 and area < 4000:

bx = (minc, maxc, maxc, minc, minc)

by = (minr, minr, maxr, maxr, minr)

ax.plot(bx, by, '-r', linewidth=2)

count += 1

#Counting the number of fruits

ax.set_title("Number of Box : {}".format(count))

ax.imshow(image, alpha = 0.5)

bounding_box(sudoku_image)

This code will add bounding boxes to the detected digits in the image. The coordinates of the boxes can be as slicing index to produce the numbers are images. These images are then read by the neural network to predict the digits.

**Apply Convolutional Neural Network to predict the digits.**

There are different datasets available to train a neural network in digit recognition. There are also OCR tools to read numbers from images. In this post, we used the MNIST handwritten dataset in predicting the numbers from images. Sounds ironic since the sudoku digits are not handwritten. We chose this dataset anyway because it has the largest dataset and produces the highest accuracy on test data (the test data refers to recognizing the sudoku digits)

There are numerous sources on how to train a neural network using the MNIST dataset. This is the most useful reference for me: https://machinelearningmastery.com/how-to-develop-a-convolutional-neural-network-from-scratch-for-mnist-handwritten-digit-classification/

You can use the CNN model to predict the digits. Take note that you need to reshape first the image before predicting the image. You may do this by using this code:

from skimage.transform import resize

import numpy as npimage = resize(image, (28, 28), anti_aliasing=True)

image = image.reshape(1,28,28,1)

As you can see, we can use a neural network to predict the numbers represented by the images.

We can then map out the location of these numbers by using the coordinates of the bounding boxes. In summary, the process converts the sudoku image into a 9x9 array. This array shall be used as input to py-sudoku, a library for solving a sudoku puzzle.

**Apply py-sudoku in solving the puzzle**

Applying py-sudoku is straightforward. You just need to input a 9x9 array into the program, then the library will give you the solution. You need to install this on your machine via pip install.

`from sudoku import Sudoku`

board = [[5, 3, 0, 0, 7, 0, 0, 0, 0],

[6, 0, 0, 1, 9, 5, 0, 0, 0],

[0, 9, 8, 0, 0, 0, 0, 6, 0],

[8, 0, 0, 0, 6, 0, 0, 0, 3],

[4, 0, 0, 8, 0, 3, 0, 0, 1],

[7, 0, 0, 0, 2, 0, 0, 0, 6],

[0, 6, 0, 0, 0, 0, 2, 8, 0],

[0, 0, 0, 4, 1, 9, 0, 0, 5],

[0, 0, 0, 0, 8, 0, 0, 7, 9]]

puzzle = Sudoku(3, 3, board=board)

puzzle.solve().show()

There are many things that can be improved from this approach. For instance, we can use homography to read images on non orthogonal views of the images, balancing techniques on dark captured images, and filters on images with noise. Moreover, we can use opencv and other similar libraries to have a real time sudoku solver on a camera. That is for later. Thanks for reading this post.