# Building a simple SUDOKU Solver from scratch - Part 1: Grid Detection & Digit Extraction

Hi, today I’m gonna explain how to build a simple SUDOKU Solver taken from image step-by-step. You can see the demo of SUDOKU Solver in the GIF image below.

To build this program, we will go through 4 main steps.

1. SUDOKU Grid Detection and Digit Extraction
2. Recognize Number with Support Vector Machine (SVM)
3. Solving SUDOKU with Backtracking Algorithm
4. Completing the simple SUDOKU Solver

This program was built by Python 2.7 and OpenCV 2.4.13 so before you want to follow this post, please install Python 2.7 and OpenCV 2.4.13 Update: Since some people asked me to modify the code to work with OpenCV 3.x, please refer to this link if you’re using OpenCV 3.x SUDOKU_OpenCV3

## 1. SUDOKU Gird Detection and Digit Extraction

The most important thing to solve a SUDOKU board from images is detecting SUDOKU grid (or line). I found many ways to extract digit from SUDOKU on the internet, but I saw this article (http://jponttuset.cat/solving-sudokus-like-a-pro-1/) is the smartest and easy way to extract digit from SUDOKU board. I took the idea from that guy and re-implement myself with Python. Let’s get started!

We will use a famous and simple technique called Hough Line Transform to detect lines on the image. If you’re not familiar with Hough Line Transform, please check out my previous article about Hough Line Transform

Note: We can visit this website to print any SUDOKU images for practicing: http://show.websudoku.com/

From an RGB frame captured from the webcam, we will convert it to a grayscale image. After that, extract edges using Canny Edge detection and then apply Hough Line Transform to detect lines. We use cv2.HoughLines() with $$\rho$$ unit equal to $$2$$ and minimum length of line to be detected is $$300$$ pixels. It means increasing the accumulator by $$2$$ when a point is satisfied and consider to be a line when the minimum value in the accumulator is $$300$$. The result will look like this:

Fig. 1. Line detection using Hough Line Transform

The next step is looking for intersections between these lines. When we know the intersection points, we can extract every block that contains SUDOKU digit.

Hmm … Look at that! There are too many lines. Synonymous with there are some redundant lines (some lines are overlapped each other).
But wait, we already know the distance of each line to the origin. It means we can easily remove the overlapped lines if the distance between these lines is close to each other.
Let’s say we will remove the redundant lines if the distance between these lines is less than $$10$$. Firstly, let’s sort these line increasingly by the distance ($$\rho$$) and then check the distance of every $$2$$ lines. If the distance is less than $$10$$, remove the second line.
You can read the following code

# HOW TO USE
# Use this with a printed SUDOKU Grid
# Press ESC key to Exit
import cv2
import numpy as np

ratio2 = 3
kernel_size = 3
lowThreshold = 30

cv2.namedWindow("SUDOKU Solver")
vc = cv2.VideoCapture(0)
if vc.isOpened(): # try to get the first frame
else:
rval = False
while rval:
# Preprocess image, convert from RGB to Gray
sudoku1 = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
sudoku1 = cv2.blur(sudoku1, (3,3))
# Apply Canny edge detection
edges = cv2.Canny(sudoku1, lowThreshold, lowThreshold*ratio2, kernel_size)
# Apply Hough Line Transform, return a list of rho and theta
lines = cv2.HoughLines(edges, 2, cv2.cv.CV_PI /180, 300, 0, 0)
if (lines is not None):
lines = lines[0]
lines = sorted(lines, key=lambda line:line[0])
# Define the position of horizontal and vertical line
pos_hori = 0
pos_vert = 0
for rho,theta in lines:
a = np.cos(theta)
b = np.sin(theta)
x0 = a*rho
y0 = b*rho
x1 = int(x0 + 1000*(-b))
y1 = int(y0 + 1000*(a))
x2 = int(x0 - 1000*(-b))
y2 = int(y0 - 1000*(a))
# If b > 0.5, the angle must be greater than 45 degree
# so we consider that line as a vertical line
if (b>0.5):
# Check the position
if(rho-pos_hori>10):
# Update the position
pos_hori=rho
cv2.line(frame,(x1,y1),(x2,y2),(0,0,255),2)
else:
if(rho-pos_vert>10):
pos_vert=rho
cv2.line(frame,(x1,y1),(x2,y2),(0,0,255),2)

# Show the result
cv2.imshow("SUDOKU Solver", frame)
key = cv2.waitKey(20)
if key == 27: # exit on ESC
break
vc.release()
cv2.destroyAllWindows()


Now, the result looks better than before.

Fig. 2. SUDOKU Grid after removing redundancy lines

Next, we will find the intersection points based on those lines. Just to recap again, every line is satisfied this equation: $$\rho=x\cos \theta+y\sin \theta$$ (1)
We have $$\rho$$ and $$\theta$$ for each line, so it’s easy to find the intersection between 2 lines by solving linear equations. In this post, I use the $$linalg$$ library in Numpy to find the intersection points. You can check out this link to see how to use $$linalg$$ in Python: https://docs.scipy.org/doc/numpy/reference/generated/numpy.linalg.solve.html

Just change a bit of code and found the intersection points like this

Fig. 3. Intersection points detection

If we have those points, we also can extract the bouding boxes of the digit number in the SUDOKU board.

Fig. 4. Bounding block for each digit

Here is the code for digit number extraction

# HOW TO USE
# Use this with a printed SUDOKU Grid
# Press ESC key to Exit
import cv2
import numpy as np

ratio2 = 3
kernel_size = 3
lowThreshold = 30

cv2.namedWindow("SUDOKU Solver")
vc = cv2.VideoCapture(0)
if vc.isOpened(): # try to get the first frame
else:
rval = False
while rval:
# Preprocess image, convert from RGB to Gray
sudoku1 = cv2.cvtColor(frame, cv2.COLOR_BGR2GRAY)
sudoku1 = cv2.blur(sudoku1, (3,3))
# Apply Canny edge detection
edges = cv2.Canny(sudoku1, lowThreshold, lowThreshold*ratio2, kernel_size)
# Apply Hough Line Transform, return a list of rho and theta
lines = cv2.HoughLines(edges, 2, cv2.cv.CV_PI /180, 300, 0, 0)
if (lines is not None):
lines = lines[0]
lines = sorted(lines, key=lambda line:line[0])
# Define the position of horizontal and vertical line
pos_hori = 0
pos_vert = 0
# Create a list to store new bundle of lines
New_lines = []
# Store intersection points
Points = []
for rho,theta in lines:
a = np.cos(theta)
b = np.sin(theta)
x0 = a*rho
y0 = b*rho
x1 = int(x0 + 1000*(-b))
y1 = int(y0 + 1000*(a))
x2 = int(x0 - 1000*(-b))
y2 = int(y0 - 1000*(a))
# If b > 0.5, the angle must be greater than 45 degree
# so we consider that line as a vertical line
if (b>0.5):
# Check the position
if(rho-pos_hori>10):
# Update the position
pos_hori=rho
# Saving new line, 0 is horizontal line, 1 is vertical line
New_lines.append([rho,theta, 0])
else:
if(rho-pos_vert>10):
pos_vert=rho
New_lines.append([rho,theta, 1])
for i in range(len(New_lines)):
if(New_lines[i][2] == 0):
for j in range(len(New_lines)):
if (New_lines[j][2]==1):
theta1=New_lines[i][1]
theta2=New_lines[j][1]
p1=New_lines[i][0]
p2=New_lines[j][0]
xy = np.array([[np.cos(theta1), np.sin(theta1)], [np.cos(theta2), np.sin(theta2)]])
p = np.array([p1,p2])
res = np.linalg.solve(xy, p)
Points.append(res)
if(len(Points)==100):
for i in range(0,9):
for j in range(0,9):
y1=int(Points[j+i*10][1]+5)
y2=int(Points[j+i*10+11][1]-5)
x1=int(Points[j+i*10][0]+5)
x2=int(Points[j+i*10+11][0]-5)
# Saving extracted block for training, uncomment for saving digit blocks
# cv2.imwrite(str((i+1)*(j+1))+".jpg", sudoku1[y1: y2,
#                                            x1: x2])
cv2.rectangle(frame,(x1,y1),
(x2, y2),(0,255,0),2)
# Show the result
cv2.imshow("SUDOKU Solver", frame)