MLearning.ai
Published in

MLearning.ai

Sudoku Solver — with source code — Fun project — Easiest Way

So guys, in today’s blog we will see how we can implement Sudoku Solver using Computer Vision and Image Processing techniques. So without any further due.

Read the full article with source code here — https://machinelearningprojects.net/sudoku-solver/

SUDOKU SOLVER
SUDOKU SOLVER

Let’s do it…

Code for Sudoku Solver…

import cv2
import imutils
from imutils.perspective import four_point_transform
from skimage.segmentation import clear_border
from tensorflow.keras.models import load_model
import numpy as np
from Sudoku import solveSudoku
from tensorflow.keras.preprocessing.image import img_to_array
import matplotlib.pyplot as plt

# Sudoku Solver
model = load_model('model/model_mnist/')
img_path = 'sudoku images/6.png'
img_shape = [28,28]

def find_puzzle(img):
real = img.copy()
gray = cv2.cvtColor(img,cv2.COLOR_BGR2GRAY)
blur = cv2.GaussianBlur(gray,(7,7),1)

thresh = cv2.adaptiveThreshold(blur,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C,cv2.THRESH_BINARY,11,2)
thresh = cv2.bitwise_not(thresh)

cnts = cv2.findContours(thresh.copy(),cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
cnts = imutils.grab_contours(cnts)
cnts = sorted(cnts,key=cv2.contourArea,reverse=True)

puzzle_cnt = None

for c in cnts:
peri = cv2.arcLength(c,True)
approx = cv2.approxPolyDP(c,0.02*peri,True)
if len(approx)==4:
puzzle_cnt=approx
break

if puzzle_cnt is None:
raise Exception(("Could not find Sudoku puzzle outline.Try debugging your thresholding and contour steps."))

cv2.drawContours(real, [puzzle_cnt], -1, (0, 255, 0), 2)

puzzle = four_point_transform(img, puzzle_cnt.reshape(4, 2))
warped = four_point_transform(gray, puzzle_cnt.reshape(4, 2))

return puzzle,warped



def extract_digit(cell):
thresh = cv2.threshold(cell,0,255,cv2.THRESH_BINARY_INV|cv2.THRESH_OTSU)[1]
thresh = clear_border(thresh) #just clear the extra white pixels along the border


cnts = cv2.findContours(thresh.copy(), cv2.RETR_EXTERNAL,cv2.CHAIN_APPROX_SIMPLE)
cnts = imutils.grab_contours(cnts)

# if no contours were found than this is an empty cell
if len(cnts) == 0:return None

# otherwise, find the largest contour in the cell and create a mask for the contour
c = max(cnts, key=cv2.contourArea)
mask = np.zeros(thresh.shape, dtype="uint8")
cv2.drawContours(mask, [c], -1, 255, -1)

(h, w) = thresh.shape
percentFilled = cv2.countNonZero(mask) / float(w * h)

# if less than 3% of the mask is filled then we are looking at noise and can safely ignore the contour
if percentFilled < 0.03:return None

# apply the mask to the thresholded cell
digit = cv2.bitwise_and(thresh, thresh, mask=mask)
kernel = np.ones((1,1),np.uint8)
digit = cv2.dilate(digit,kernel,iterations=1)

# return the digit to the calling function
return digit


def display_numbers_on_board(board,puzzle):
x = puzzle.copy()
k = 0
for i in range(9):
for j in range(9):
startX,startY,endX,endY = cell_locs[k]
testX = int((endX - startX) * 0.33)
testY = int((endY - startY) * -0.2)
testX += startX
testY += endY
cv2.putText(x,str(board[i][j]),(testX,testY),cv2.FONT_HERSHEY_SIMPLEX,0.9,(0,0,255),2)
k+=1
plt.figure(figsize=(10,8))
plt.imshow(x)
plt.xticks([])
plt.yticks([])
plt.show()
return x

img = cv2.imread(img_path)
img = imutils.resize(img,width=600)

puzzle,warped = find_puzzle(img)
puzzle = imutils.resize(puzzle,width=600)
warped = imutils.resize(warped,width=600)

step_x = warped.shape[1]//9
step_y = warped.shape[0]//9

board = np.zeros(shape=(9,9),dtype='int')
cell_locs = []

for i in range(9):
for j in range(9):
topleftx = j*step_x
toplefty = i*step_y
rightendx= (j+1)*step_x
rightendy = (i+1)*step_y
cell = warped[toplefty:rightendy, topleftx:rightendx]
digit = extract_digit(cell)
if digit is not None:
roi = cv2.resize(digit,tuple(img_shape))
roi = roi.astype('float')/255.0
roi = img_to_array(roi)
roi = np.expand_dims(roi,axis=0)
pred = model.predict(roi).argmax(axis=1)[0]
board[i,j] = pred
cell_locs.append([topleftx,toplefty,rightendx,rightendy])



_=display_numbers_on_board(board,puzzle)

while 1:
res = input('Are all numbers predicted correctly? (y/n)')
if res=='n':
cx,cy,ele = input('Input row no, col no, correct element of cell For eg. --> 1 2 1: ').split()
try:
board[int(cx),int(cy)] = int(ele)
except:
print('out of range...')
_ = display_numbers_on_board(board,puzzle)
elif res=='y':
break
else:
print('Wrong choice!!!')

solved = solveSudoku(board)

x = display_numbers_on_board(board,puzzle)
cv2.imshow('solved',x)

cv2.waitKey(0)
cv2.destroyAllWindows()
  • Line 1–10 — Importing libraries required for Sudoku Solver.
  • Line 12–14 — Load mnist model and the sudoku image. Also declare a constant img_shape which will be the size of our sudoku image after resizing.
  • Line 16–45 — This function will find the puzzle in the image through Image Processing techniques.
  • Read the image, convert it to grayscale, and then apply Gaussian Blur to remove Gaussian Noise.
  • The threshold the image and inverse it. Means convert white to black and black to white.
  • Then find the contours and extract the biggest contour in the image. This is probably our sudoku.
  • Apply four point transformation to get the straight view of the puzzle and return it.
  • Line 49–77 — This function will extract the digit cell from the puzzle and return it so that the mnist model could identify the number in it.
  • Line 80–97 — This function will simply put the numbers on the image/board.
  • Line 99–100 — Simply read and resize the image.
  • Line 102–104 — Extract the puzzle and resize it.
  • Line 106–107 — This will tell us the step size we have to take in the x and y-direction. This step is basically the cell size in the x and y directions respectively.
  • Line 109 — Create the board with all values initialized with 0s.
  • Line 110 — Create array cell_locs which will contain the cell locations/coordinates.
  • Line 112–127 — Traverse in the 9*9 loop where the first 9 represents the 9 rows of the board and the second 9 represents the 9 columns of the board. On traversing it will extract the cell images, predict the number using mnist and put that number in the board array we created in Line 109. Also, we will keep on storing the cell locations in the cell_loc array.
  • Line 133–145 — If by chance any of the numbers is wrongly predicted by the mnist, correct it.

NOTE — The numbers in blue are predicted numbers for that cell. The text in red is the address of that cell. If any number is wrongly classified by mnist, correct that. Like the first wrong classified number is at (4,7). The original number there is 1 but the mnist said it is 7 so we will correct it first.

  • Line 147 — Solve the sudoku using the solveSudoku function that we imported from Sudoku.py. This Sudoku.py is also written by me and I have used Backtracking for solving sudoku.
  • Line 149–150 — Display the solved sudoku numbers on the final image and display it.
  • Line 152–153 — Destroy all windows.

Final result of Sudoku Solver…

SUDOKU SOLVER
SUDOKU SOLVER

Do let me know if there’s any query regarding the Sudoku Solver by contacting me on email or LinkedIn. You can also comment down below for any queries.

To explore more Machine Learning, Deep Learning, Computer Vision, NLP, Flask Projects visit my blog — Machine Learning Projects

For further code explanation and source code visit here — https://machinelearningprojects.net/sudoku-solver/

So this is all for this blog folks, thanks for reading it and I hope you are taking something with you after reading this and till the next time 👋…

Read my previous post: HUMAN SEGMENTATION USING U-NET

--

--

--

Data Scientists must think like an artist when finding a solution when creating a piece of code. ⚪️ Artists enjoy working on interesting problems, even if there is no obvious answer ⚪️ linktr.ee/mlearning 🔵 Follow to join our 18K+ Unique DAILY Readers 🟠

Recommended from Medium

Find All Anagrams in a String

Creating Collections Strapi Backend

Meet the team: Design and Photography

Service objects in Rails

Windows Networking Troubleshooting 7: Network Connectivity Debugging (TrackNblOwner Principle)

Azure Data Factory: Handle Dynamic Column Names With Rule-Based Mapping In Data Flow

Sample CSV dataset

JIRA project

Spring Framework Fundamentals in Examples

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
Abhishek Sharma

Abhishek Sharma

Data Scientist || Blogger || machinelearningprojects.net

More from Medium

NEURAL STYLE TRANSFER — WITH SOURCE CODE — EASIEST EXPLANATION — FUN PROJECT

NEURAL STYLE TRANSFER

Deep Learning in Medicine: Identifying Pneumonia from a Chest-X-Ray

Fix Attribute Error and Runtime Error in tensorflow and keras | Beginner Must Read

More is not always good — Eye disease classification