Sudoku Solver using Computer Vision and Deep Learning — Part 1

The rules of the game:

It’s all about putting digits between 1 and 9 into a square, 9x9 grid, subdivided into 9 boxes. But The value of a cell cannot be repeated amongst any of its peers.

Input image for sudoku solver

A: Extract the sudoku from the image

We need to do a bit of image processing before proceeding further.

1: Pre Processing the image

First, we apply Gaussian blur with a kernel size (height, width) of 9 to the image. Note that kernel sizes must be positive and odd and the kernel must be square. Then we use adaptive threshold using 11 nearest neighbour pixels.

proc = cv2.GaussianBlur(img.copy(), (9, 9), 0)
proc = cv2.adaptiveThreshold(proc, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 11, 2)
proc = cv2.bitwise_not(proc, proc)  
kernel = np.array([[0., 1., 0.], [1., 1., 1.], [0., 1., 0.]],np.uint8)
proc = cv2.dilate(proc, kernel)
Sudoku image after thresholding

2: Find the corners of the largest polygon

Next step is to find the 4 extreme corners of the largest contour in the image. So we will find all the contours, sort by area in descending order and pick the one with the largest area.

_, contours, h = cv2.findContours(img.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
contours = sorted(contours, key=cv2.contourArea, reverse=True)
polygon = contours[0]
bottom_right, _ = max(enumerate([pt[0][0] + pt[0][1] for pt in
polygon]), key=operator.itemgetter(1))
top_left, _ = min(enumerate([pt[0][0] + pt[0][1] for pt in
polygon]), key=operator.itemgetter(1))
bottom_left, _ = min(enumerate([pt[0][0] - pt[0][1] for pt in
polygon]), key=operator.itemgetter(1))
top_right, _ = max(enumerate([pt[0][0] - pt[0][1] for pt in
polygon]), key=operator.itemgetter(1))
[polygon[top_left][0], polygon[top_right][0], polygon[bottom_right][0], polygon[bottom_left][0]]
4 corners of the largest polygon

3: Crop and Warp Image

Now that we have all the 4 coordinates of sudoku, we will crop and warp a rectangular section from an image into a square of similar size. The rectangle described by the top left, top right, bottom right and bottom left points.

top_left, top_right, bottom_right, bottom_left = crop_rect[0], crop_rect[1], crop_rect[2], crop_rect[3]
src = np.array([top_left, top_right, bottom_right, bottom_left], dtype='float32')
side = max([ distance_between(bottom_right, top_right),
distance_between(top_left, bottom_left),
distance_between(bottom_right, bottom_left),
distance_between(top_left, top_right) ])
def distance_between(p1, p2): 
a = p2[0] - p1[0]
b = p2[1] - p1[1]
return np.sqrt((a ** 2) + (b ** 2))
dst = np.array([[0, 0], [side - 1, 0], [side - 1, side - 1], [0, side - 1]], dtype='float32')
m = cv2.getPerspectiveTransform(src, dst)
cv2.warpPerspective(img, m, (int(side), int(side)))
Sudoku image after crop and warp perspective transform

4: Infer grid from the square image

Infers 81 cell grid from a square image. We swap j and i here so the rectangles are stored in the list reading left-right instead of top-down.

squares = [] 
side = img.shape[:1]
side = side[0] / 9
for j in range(9):
for i in range(9):
p1 = (i * side, j * side) #Top left corner of a box
p2 = ((i + 1) * side, (j + 1) * side) #Bottom right corner
squares.append((p1, p2)) return squares

5: Get each digit

Next step is to extracts digits from their cells and builds an array.

digits = []
img = pre_process_image(img.copy(), skip_dilate=True)
for square in squares:
digits.append(extract_digit(img, square, size))
def extract_digit(img, rect, size):
digit = cut_from_rect(img, rect)
h, w = digit.shape[:2]
margin = int(np.mean([h, w]) / 2.5)
_, bbox, seed = find_largest_feature(digit, [margin, margin], [w
- margin, h - margin])
digit = cut_from_rect(digit, bbox)

w = bbox[1][0] - bbox[0][0]
h = bbox[1][1] - bbox[0][1]

if w > 0 and h > 0 and (w * h) > 100 and len(digit) > 0:
return scale_and_centre(digit, size, 4)
else:
return np.zeros((size, size), np.uint8)
Final sudoku image

--

--

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