# Sudoku Solver using OpenCV and DL — Part 2

Source: Deep Learning on Medium

If you’re impatient, scroll to the bottom of the post for the Github Repos

This is Part 2 of Sudoku Solver. Make sure you got a glimpse of Part 1. So moving ahead, till now we have preprocessed an image i.e., take an image and perform a crop and warp perspective transform. Now we need to extract the numbers and solve the sudoku.

### 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.

For digit recognition, we will be training neural network over MNIST dataset containing 60,000 images of digits from 0 to 9.

We will start by importing all the libraries.

`import numpyimport 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 Kimport matplotlib.pyplot as plt`

We will fix random seed for reproducibility.

`K.set_image_dim_ordering('th')`
`seed = 7numpy.random.seed(seed)(X_train, y_train), (X_test, y_test) = mnist.load_data()`

Now, let’s reshape the images to be samples*pixels*width*height and normalize inputs from 0–255 to 0–1. After this, we will one hot encode the outputs.

`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 / 255X_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]`

Next, we will create a model to predict the handwritten digit.

`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'))`

After creating the model, let’s compile it and fit over the dataset and evaluate it.

`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))`

Now, we will test the above model created.

`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()`

The accuracy of the neural network was 98.314%. At last, we will save the sequential model so that we don’t have to train it over and over whenever we want to use it.

`# serialize model to JSONmodel_json = model.to_json()with open("model.json", "w") as json_file: json_file.write(model_json)# serialize weights to HDF5model.save_weights("model.h5")print("Saved model to disk")`

To know more about Handwritten Digit Recognition https://github.com/aakashjhawar/Handwritten-Digit-Recognition

Our next step will be to load the pre-trained model and weights.

`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")`

Then we will resize the image and split the image into 9×9 small images. Each small image will be of a digit from 1- 9.

`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)`

identify_number function takes an image of digit and predicts the digit in the image.

`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]`

After performing the above steps our Sudoku grid will look like:

### C: Compute the solution of the sudoku using Backtracking Algorithm

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

Search the grid to find an entry that is still unassigned. If found, the reference parameters row, col will be set the location that is unassigned, and true is returned. If no unassigned entries remain, false is returned. ‘l’ is a list variable that has been passed from the solve_sudoku function to keep track of incrementation of rows and columns.

`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`

Returns a boolean which indicates whether any assigned entry in the specified row matches the given number.

`def used_in_row(arr,row,num): for i in range(9):  if(arr[row][i] == num):  return True return False`

Returns a boolean which indicates whether any assigned entry in the specified column matches the given number.

`def used_in_col(arr,col,num): for i in range(9):  if(arr[i][col] == num):  return True return False`

Returns a boolean which indicates whether any assigned entry within the specified 3×3 box matches the given number.

`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`

Checks whether it will be legal to assign num to the given (row, col). Returns a boolean which indicates whether it will be legal to assign num to the given (row, col) location. Check if ‘num’ is not already placed in the current row, current column and current 3×3 box.

`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)`

Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes). ‘l’ is a list variable that keeps the record of row and col in find_empty_location function. Assigning list values to row and col that we got from the above function.

`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`

The last thing is to print the grid.

`def print_grid(arr): for i in range(9): for j in range(9):  print (arr[i][j])  print ('\n')`

Now, let’s stitch all the functions in the main function.

`def sudoku_solver(grid): if(solve_sudoku(grid)): print('---') else: print ("No solution exists") grid = grid.astype(int) return grid`

The output of this function will be our solved sudoku.

### 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 https://github.com/aakashjhawar/SolveSudoku. Drop me a note if you find it useful or have any follow-up questions. Thanks!