Sudoku Solver (Part 2)

Anmol Dua

In previous part, we have successfully extracted the sudoku from the camera image. In this part we will we be extracting the cells ,get the numbers from the cells and solve sudoku and give the final solved sudoku.

Image of sudoku that we have extracted from the camera image is shown below and we will be doing further processing in this image.

Sudoku from the last post

Step1 : Extract the cells

Lets make a function which will take this image and extract cells from it and store these cells in some folder. Let say the defination of function looks like this:

def extract_cells(sudoku): 

Here in this function you will be passing array of image after reading it using opencv.

Now all the code that I will explain now in this step will be a part of this function (extract_cells).

W,H = sudoku.shape
sudoku = cv2.resize(sudoku , (min(W,H) , min(W,H)))
cell_size = int(W/9)

As we can see that we have to solve 3x3 grid sudoku .So that basically means there are 9 cells vertically and horizontally in each column and row respectively. By this we can get the side length of 1 cell as:

Side length of 1 Cell = ( Side Length of Sudoku / 9)

We know that sudoku is of square shape and height = width of sudoku but sometimes extracted image of sudoku from previous image processing is not square so to eliminate that problem of sudoku first take width and height of current sudoku and resize the image of sudoku with side length minimum of height and width. By this processing we gurantee that now shape of sudoku image is square and after that we can get the proper cell size.

i,j = 0,0
if (cell_size != 0):
for r in range(0,W-cell_size,cell_size):
row = []
j = 0
for c in range(0,W-cell_size,cell_size):
cell = sudoku[r+10:r+cell_size-10, c+10: c+cell_size-10]
cv2.imwrite('./cells/'+str(i)+':'+str(j)+'.png' , cell)
j = j+1
i = i+1

In this code the basic idea is looping through column and rows which I think code explains very clearly and extracting out each and every cell from sudoku and storing those cells inside a folder (which currently I have named as cells ) where the name of cropped image will be given as:

( row_number : col_number ) => Name of every cropped cell will be in this format.

Example : 0:0.png => Name of row 0 and col 0 cropped cell from sudoku image which corresponds to number 5. Extracted image is shown below for row 0 and col 0.

0:0.png

Example 2 : Image for extracted cell for row 1and col 3 is shown as below:

Note :: we have start the count of row and column from 0 not from 1.

By Extracting all these cells and storing them inside folder you will get a total of 81 images which contains blank + number images.

Step2 : Train To Detect Number and Blanks

Till now we have extracted the cell image from sudoku image and stored them inside the cells folder. Now we have to detect the numbers for each cell image.To do this we have to train a classification model on some dataset to achieve this task. Here I am using Chars74k image dataset and MobileNet as a classification model.

Summary of MobileNet

  • Lightweight Architecture
  • It is a stack of seperable convolution modules.
  • Seperable Convolution Module comprises of depth wise convolution and conv 1x1 (pointwise convolution)
  • Depthwise Convolution : Convolution is performed independantly for each input channels. Depthwise convolution significantly reduces the
    computational cost by omitting convolution in channel domain. It performs a single convolution on each color channel rather than
    combining all three and flatening it.

Download the dataset( make sure that you are downloading the computer fonts category data ) and extract out only the numbers folder (0–9). You notice that images in this dataset have numbers in black and background in white.

We know that sudoku only contains number between (1–9) so why are we taking 0 in dataset.Thats because we have to take one class for blank cells also.So what we do is make those 0 numbered images in 0 class images as blank (no number) images by doing any image processing. I have done dilation with bigger filter and more number of iteration. You can do that by some other way , just make sure whole background of images must be white. After this, split the dataset into train and validation folder. After dataset preparation task ,it’s time to train the model.

  1. As a first step to train the model import all libraries in your code.
import keras
from keras import backend as K
from keras.layers.core import Dense, Activation
from keras.optimizers import Adam
from keras.metrics import categorical_crossentropy
from keras.preprocessing.image import ImageDataGenerator
from keras.preprocessing import image
from keras.models import Model
from keras.applications import imagenet_utils
from keras.layers import Dense,GlobalAveragePooling2D
from keras.applications import MobileNet
from keras.applications.mobilenet import preprocess_input
import numpy as np
from IPython.display import Image
from keras.optimizers import Adam
from keras.callbacks import ModelCheckpoint, LearningRateScheduler, TensorBoard, EarlyStopping
from keras.layers import Dropout, Flatten

2 . Now intialize the MobileNet model. I have taken weights to be none because we will be training this model with randomly set weights and also I have set input shape as (43,43,3).I have set this input shape because I know the size of each and every cell image of sudoku that I have extracted and I found out that most of these images are in (43,43,3) size so I have trained dataset images on this input shape.One Last thing is that I am not taking last layers of mobile net as i have set include_top = False.

base_model=
MobileNet(weights=None,include_top=False,input_shape=(43,43,3))

Now it’s time to add our own custom last layers for our use case. I have made these layers. You can add your own layers , just make sure that last layer (output) contains 10 neurons.

x = base_model.output
x = Flatten()(x)
x = Dense(512, activation="relu")(x)
x = Dropout(0.2)(x)
x = Dense(128, activation="relu")(x)
x = Dropout(0.25)(x)
x = Dense(32, activation="relu")(x)
preds = Dense(10,activation='softmax')(x)

It’s time to initialize the ImageDataGenerator for generating batches of tensor images. We will be making this for both training and validation directory.Below code is for training generator.

train_datagen=ImageDataGenerator(rescale = 1./255)train_generator=
train_datagen.flow_from_directory('./training_dir/',
target_size=(43,43),
batch_size=32,
class_mode='categorical',
shuffle=True)

This code is for validation generator.

test_datagen=ImageDataGenerator(rescale = 1./255)validation_generator = test_datagen.flow_from_directory(
'./validation_dir/',
target_size = (43,43),
class_mode = "categorical")

Now initialize the model and compile it.

model=Model(inputs=base_model.input,outputs=preds)
model.compile(optimizer='Adam',loss='categorical_crossentropy',metrics=['accuracy'])

Also define model checkpoint and early stopping.

checkpoint = ModelCheckpoint("weights3.h5", monitor='val_acc', verbose=1, save_best_only=True, save_weights_only=False, mode='auto', period=1)early = EarlyStopping(monitor='val_acc', min_delta=0, patience=10, verbose=1, mode='auto')

That’s it , now just train the data after all the configurations:

BATCH_SIZE = 32
fit_history = model.fit_generator(
train_generator,
steps_per_epoch = 9000 // BATCH_SIZE,
epochs=50,
validation_data = validation_generator,
validation_steps = 1000// BATCH_SIZE,
callbacks = [checkpoint],
initial_epoch = 0)

After training you have weights just download it as we will be using that in our sudoku solver.

Till now all the code you see for training was according to my configuration that I have set if you want another configuration or want to try different model you can do that. But make sure that your config works and model that you are choosing is practical for running in CPU.I have used mobile net because it reduces the computation cost with a factor of 1/9 then the standard convolution.

Step3 : Detect Number and Blank From Cell Images

Function for detecting number from images from cells directory is shown below :

def extractDigits(path_dir):
paths = glob.glob(path_dir + '/*.png')
d = [[0 for i in range(9)] for i in range(9)]
for i in paths:
g = i.split('/')[-1].replace('.png','')
x = cv2.imread(i)
x = cv2.bitwise_not(x)
kernel = np.ones((3,3),np.uint8)
x = cv2.dilate(x,kernel,iterations = 1)
x = cv2.erode(x,kernel,iterations = 2)
cv2.imwrite('./check/'+i.split('/')[-1],x)
n = getResult('./check/'+i.split('/')[-1])
n = NumberAssign(n)
a = int(g.split(':')[0])
b = int(g.split(':')[1])
if (n == 0):
d[a][b] = 0
else:
d[a][b] = n
return d

In the above function what we are doing is first we are getting all the png images from the specified path and store that list of images in variable called paths.Make a matrix of 9x9 and intialize all its value to 0. You can see that the matrix that I am talking about is named as d.

Iterating through the list and getting image_paths. After getting image_path, read the image after that applying bitwise_not to the image for getting the inverse of current image as the current image contains black as a background and white as a digit and inverse of current image will now have white as a background and black as a digit . I have inverse this because I have trained the model on inverse images. After that to make digit more clearly visible without noise I have applied 3x3 kernel dilation with an iteration of 1 followed by an erosion operation of 3x3 kernel with an iteration of 2 then after that storing the image and getting the prediction corresponding to that image with our trained model. So the digit prediction will be saved in our variable n as shown in code above. We are getting the row-number and col-number from the image name that we have saved before.Here a variable is row-number and b variable is col-number. If we get digit prediction(n) as 0 that means the image does not contains any digit so setting those values as 0 otherwise setting those values as a predicted number. After that I am returning the matrix.

Step4 : Solving Sudoku using Backtracking

Now its time to solve sudoku as we got the matrix from the above function. To solve sudoku I will use the concept of backtracking in recursion. Lets see the code along with explanation.

import math
def SolveSudokuMain(mat , n = 9):
if(not SolveSudoku(mat,0,0,n)):
print ("No Solution Exists !!")

This is the function in which we are passing the matrix . In this function we are passing the matrix to the another function which will return the boolean (True if the matrix is solved successfully and False if not). I am printing “No Solution Exists!!” if SolveSudoku function returns False.

def isSafe(mat,i,j,no,n):
for k in range(0,n):
if(mat[i][k] == no or mat[k][j] == no):
return False
sqn = math.sqrt(n)
sx = (i//sqn)*sqn
sy = (j//sqn)*sqn
for x in range(int(sx),int(sx+sqn)):
for y in range(int(sy),int(sy+sqn)):
if(mat[x][y]==no):
return False
return Truedef SolveSudoku(mat,i,j,n):
if(i == n):
for k1 in range(n):
for k2 in range(n):
print (mat[k1][k2],end = " ")
print ("::")
print ("-"*30)
return True
if(j == n):
return SolveSudoku(mat,i+1,0,n)
if(mat[i][j]!=0):
return SolveSudoku(mat,i,j+1,n)
for no in range(1,n+1):
b = isSafe(mat,i,j,no,n)
if(b):
mat[i][j] = no
solveHui = SolveSudoku(mat,i,j+1,n)
if(solveHui):
return True
mat[i][j] = 0
return False

Above is the main logic to solve sudoku using recursion-backtracking in a left to right and then top to down fashion. In SolveSudoku function I am passing 4 arguments which are the matrix , current row-number , current col-number, number of rows/cols = 9. Just check the recursion portion first of above SolveSudoku function :

if(mat[i][j]!=0):
return SolveSudoku(mat,i,j+1,n)
for no in range(1,n+1):
b = isSafe(mat,i,j,no,n)
if(b):
mat[i][j] = no
solveHui = SolveSudoku(mat,i,j+1,n)
if(solveHui):
return True
mat[i][j] = 0
return False

Here first I check whether the current cell contains a number other than 0 (Note : 0 here means that the cell is empty). If yes then recur to the next column. If no , then check for each possibility by setting the number 1 to 9 , this is achieved by looping through 1 to 9 and setting number to the cell and recuring to the next column and check whether the next column is returning true or not. If it is returning true then that means till now sudoku is solved by setting this number so I will return true otherwise if it return false then set another number and repeat the same process. If every number 1 to 9 is returning false then I have to set that cell as 0 to blank and retuning false as we are telling the previous function call which is in a call stack that sudoku is not solved with the number that you have set. So basically this is the main idea that is used here to solve sudoku.

Now we need to check the base cases which is shown below :

if(i == n):
for k1 in range(n):
if(k1%3 == 0 and k1 != 0):
print ('___'*30)
for k2 in range(n):
if(k2%3 == 0):
print (' | ',end = "")
print (mat[k1][k2],end = " ")
print ('')
return True
if(j == n):
return SolveSudoku(mat,i+1,0,n)

As we are going left to right and then top to bottom fashion just visualize all these basecases carefully that I am talking about below.

Here I am checking whether the (current row_number == number of rows + 1). If it is then that means we have solved the sudoku and will print the sudoku and returns True so that earlier calls can get notified about it.

After this , now in 2nd base case I am checking whether the current col_number == number of col + 1). If it is then that means we have iterated the whole row and now it’s time to go down thats why see carefully I am passing i+1 as a row-number and 0 as col-number.

One Last thing how to check whether the current number that we are setting to the empty cell is solving sudoku. This checked using function isSafe that is shown below :

def isSafe(mat,i,j,no,n):
for k in range(0,n):
if(mat[i][k] == no or mat[k][j] == no):
return False
sqn = math.sqrt(n)
sx = (i//sqn)*sqn
sy = (j//sqn)*sqn
for x in range(int(sx),int(sx+sqn)):
for y in range(int(sy),int(sy+sqn)):
if(mat[x][y]==no):
return False
return True

In this function I am passing 5 arguments : current matrix , current row number , current col number , current number that you have set , number of rows/cols = 9. Basically the main idea to solve sudoku is written here where I have to check whether the number that I am writing into the cell is not there in a whole row , whole column or inside a grid.

After solving the whole sudoku output will look like this inside a terminal:

This is the solved sudoku on terminal

Hence we have done how to take pictures of sudoku and solve them.

Thank you.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade