Sudoku Solver using OpenCV and DL — Part 2

Original Sudoku image and pre performed image

B: Extract each number present in the image

So, our next task is to extract each number from the image, identify the number and save it into a 2D matrix.

import numpy
import cv2from keras.datasets
import mnistfrom keras.models
import Sequentialfrom keras.layers
import Densefrom keras.layers
import Dropoutfrom keras.layers
import Flattenfrom keras.layers.convolutional
import Conv2Dfrom keras.layers.convolutional
import MaxPooling2Dfrom keras.utils
import np_utilsfrom keras
import backend as K
import matplotlib.pyplot as plt
K.set_image_dim_ordering('th')seed = 7numpy.random.seed(seed)
(X_train, y_train), (X_test, y_test) = mnist.load_data()
X_train = X_train.reshape(X_train.shape[0], 1, 28,
28).astype('float32')
X_test = X_test.reshape(X_test.shape[0], 1, 28,
28).astype('float32')
X_train = X_train / 255
X_test = X_test / 255
y_train = np_utils.to_categorical(y_train)
y_test = np_utils.to_categorical(y_test)
num_classes = y_test.shape[1]
model = Sequential()
model.add(Conv2D(32, (5, 5), input_shape=(1, 28, 28),
activation='relu'))
model.add(MaxPooling2D(pool_size=(2, 2)))model.add(Conv2D(16, (3,
3), activation='relu'))
model.add(MaxPooling2D(pool_size=(2, 2)))
model.add(Dropout(0.2))
model.add(Flatten())
model.add(Dense(128, activation='relu'))
model.add(Dense(64, activation='relu'))
model.add(Dense(num_classes, activation='softmax'))
Summary of model
model.compile(loss='categorical_crossentropy', optimizer='adam',
metrics=['accuracy'])
model.fit(X_train, y_train, validation_data=(X_test, y_test),
epochs=10, batch_size=200)
scores = model.evaluate(X_test, y_test, verbose=0)
print("Large CNN Error: %.2f%%" % (100-scores[1]*100))
test_images = X_test[1:5]
test_images = test_images.reshape(test_images.shape[0], 28, 28)
print ("Test images shape: {}".format(test_images.shape))
for i, test_image in enumerate(test_images, start=1):
org_image = test_image
test_image = test_image.reshape(1,1,28,28)
prediction = model.predict_classes(test_image, verbose=0)
print ("Predicted digit: {}".format(prediction[0]))
plt.subplot(220+i)
plt.axis('off')
plt.title("Predicted digit: {}".format(prediction[0]))
plt.imshow(org_image, cmap=plt.get_cmap('gray'))
plt.show()
Predicted digits of Handwritten digit classification model
# serialize model to JSON
model_json = model.to_json()
with open("model.json", "w") as json_file:
json_file.write(model_json)
# serialize weights to HDF5
model.save_weights("model.h5")
print("Saved model to disk")
json_file = open('model.json', 'r')
loaded_model_json = json_file.read()
json_file.close()
loaded_model = model_from_json(loaded_model_json)
loaded_model.load_weights("model.h5")
sudoku = cv2.resize(sudoku, (450,450))
grid = np.zeros([9,9])
for i in range(9):
for j in range(9):
image = sudoku[i*50:(i+1)*50,j*50:(j+1)*50]
if image.sum() > 25000:
grid[i][j] = identify_number(image)
else:
grid[i][j] = 0
grid = grid.astype(int)
def identify_number(image):
image_resize = cv2.resize(image, (28,28)) # For plt.imshow
image_resize_2 = image_resize.reshape(1,1,28,28) # For input to model.predict_classes
# cv2.imshow('number', image_test_1)
loaded_model_pred = loaded_model.predict_classes(image_resize_2
, verbose = 0)
return loaded_model_pred[0]
Extracted Sudoku

C: Compute the solution of the sudoku using Backtracking Algorithm

We will use Backtracking Algorithm to compute the solution of the sudoku.

def find_empty_location(arr,l):
for row in range(9):
for col in range(9):
if(arr[row][col]==0):
l[0]=row
l[1]=col
return True
return False
def used_in_row(arr,row,num):
for i in range(9):
if(arr[row][i] == num):
return True
return False
def used_in_col(arr,col,num):
for i in range(9):
if(arr[i][col] == num):
return True
return False
def used_in_box(arr,row,col,num):
for i in range(3):
for j in range(3):
if(arr[i+row][j+col] == num):
return True
return False
def check_location_is_safe(arr,row,col,num):
return not used_in_row(arr,row,num) and
not used_in_col(arr,col,num) and
not used_in_box(arr,row - row%3,col - col%3,num)
def solve_sudoku(arr):
l=[0,0]
if(not find_empty_location(arr,l)):
return True
row=l[0]
col=l[1]
for num in range(1,10):
if(check_location_is_safe(arr,row,col,num)):
arr[row][col]=num
if(solve_sudoku(arr)):
return True
# failure, unmake & try again
arr[row][col] = 0

return False
def print_grid(arr):
for i in range(9):
for j in range(9):
print (arr[i][j])
print ('\n')
def sudoku_solver(grid):
if(solve_sudoku(grid)):
print('---')
else:
print ("No solution exists")
grid = grid.astype(int)
return grid
Final solution

Conclusion

So we have finally managed to solve a Sudoku grid from the image alone. If you’ve hung in this long… thanks! I hope there’s been something valuable for you. The solver is by no means foolproof; it still has trouble with some images and either will fail to parse them or parse them incorrectly leading to failure to solve them (because it may have parsed as an invalid puzzle). The goal, of course, was to ramp up on some new technologies and the project has been valuable from that perspective. The source code is available on Github. Drop me a note if you find it useful or have any follow-up questions.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store