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

Hi there, today I'm gonna explain how to build a simple SUDOKU Solver by taking the image step-by-step. The result of SUDOKU will be shown in the current image just like this GIF image.

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

1. SUDOKU Gird Detection and Digit Extraction

The most important thing to solve a SUDOKU grid by taking image is detecting SUDOKU grid (or line) on the image. 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 by myself in Python.
So, 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 image for practicing: http://show.websudoku.com/

From a frame in the video, we will convert from RGB to Gray Scale image. After that, using Canny Edge detection to extract edges from images. And then apply Hough Line Transform to detect lines on the image. We use cv2.HoughLines() with `rho` unit `= 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`.

We will have the result 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.
But wait... Look at that! There are too many lines. Synonymous with there are some redundant lines (some lines are close together). We know the distance of each line to the origin so we can easily remove the redundant lines if the distance of these lines is close together.
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
    rval, frame = vc.read()
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)
    rval, frame = vc.read()
    key = cv2.waitKey(20)
    if key == 27: # exit on ESC
     break
vc.release()
cv2.destroyAllWindows()

Now, it looks better than Figure 1.

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 = xcostheta + ysintheta   (1)`
We have `rho` and `theta` for each line, so we can easily find the intersection between 2 lines by solving linear equations. In this topic, I use 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 point, we also can extract the bouding box of the digit number in SUDOKU board like this

Fig. 4. Bounding block for each digit

Here is the code for digit 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
    rval, frame = vc.read()
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):
            sudoku1 = cv2.adaptiveThreshold(sudoku1, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C,cv2.THRESH_BINARY_INV, 101, 1)
            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)
    rval, frame = vc.read()
    key = cv2.waitKey(20)
    if key == 27: # exit on ESC
     break
vc.release()
cv2.destroyAllWindows()

To make sure that we extract the right digit block, I set the condition is when the number of intersection points is equal to 100, we extract the point. You can check with the code above.

Bravo! Now we know how to extract digit number block from SUDOKU board. In the next article, we will recognite those digit numbers with Support Vector Machine algorithm :)