Sudoku Solver AI with OpenCV

We will be creating a Sudoku Solver AI using python and Open CV to read a Sudoku puzzle from an image and solving it. There a lot of methods to achieve this goal. Thus in this series, I have compiled the best methods I could find/research along with some hacks/tricks I learned along the way.

This article is a part of the series Sudoku Solver with OpenCV. **Part 1: Image Processing****Part 2: Sudoku and Cell Extraction****Part 3: Solving the Sudoku**

I am trying to be as detailed as possible in listing the steps along with there descriptions. There are several ways to Extract sudoku and solve it. I will add alternate ways, but won’t go into detail about them.

**Import the image****Pre Processing the Image**

2.1**Gaussian blur:**We need to gaussian blur the image to reduce noise in thresholding algorithm

2.2**Thresholding:**Segmenting the regions of the image

2.3**Dilating the image:**In cases like noise removal, erosion is followed by dilation.**Sudoku Extraction**3.1**Find Contours**3.2**Find Corners:**Using Ramer Doughlas Peucker algorithm / approxPolyDP

3.3**Crop and Warp Image:**We remove all the elements in the image except the sudoku

3.4**Extract Cells**

## 3.1 Find Contours:

We will find external contours and then sort by area in descending order. Thus, the **largest polygon is stored in contours[0]**.

**findContours:** boundaries of shapes having the same intensity**CHAIN_APPROX_SIMPLE** — stores only minimal information of points to describe the contour**RETR_EXTERNA**L: gives “outer” contours.

`for c in ext_contours:`

peri = cv2.arcLength(c, True)

approx = cv2.approxPolyDP(c, 0.015 * peri, True)

if len(approx) == 4:

# Here we are looking for the largest 4 sided contour

return approx

Tip: If you want to see the contours, try *drawcontour(..)*

## 3.2 Find Corners:

The largest contours is are the corners of the sudoku. There are several ways we can achieve this. Notable methods include Canny Edge Algorithm, Ramer Doughlas Peucker algorithm, Bounding Rectangle, and approxPolyDP.

A.** ****approxPolyDP****: **We approximate the curve given by the largest Contours. The largest 4-sided contour is the sudoku.

Function Deatils:**cv2.approxPolyDP(curve, epsilon, closed[, approxCurve])****Curve->** hers is the largest contour**epsilon ->** Parameter specifying the approximation accuracy. This is the maximum distance between the original curve and its approximation.**closed ->** If true, the approximated curve is closed. Otherwise, it is not closed.**return type: **the same type as the input curve

`peri = cv2.arcLength(c, True)`

approx = cv2.approxPolyDP(c, 0.015 * peri, True)

if len(approx) == 4:

# Here we are looking for the largest 4 sided contour

return approx

# approx has the

In corners[0],… stores the points in format [[x y]].

# Extracting the points

corners = [(corner[0][0], corner[0][1]) for corner in corners]

top_r, top_l, bottom_l, bottom_r = corners[0], corners[1], corners[2], corners[3]

return top_l, top_r, bottom_r, bottom_l# Index 0 - top-right

# 1 - top-left

# 2 - bottom-left

# 3 - bottom-right

B. **Ramer Doughlas Peucker algorithm**:

We will use max(list, key) for the right side corners as there x-value is greater. Likewise, we will use min(list, key) for the left side corners.

`operator`

is a built-in module providing a set of convenient operators. In two words `operator.itemgetter(n)`

constructs a callable that assumes an iterable object (e.g. list, tuple, set) as input, and fetches the n-th element out of it.

We will use max(list, key) for the right side corners as there x-value is greater. Likewise, we will use min(list, key) for the left side corners.

`bottom_right, _ = max(enumerate([pt[0][0] + pt[0][1] for pt in`

ext_contours[0]]), key=operator.itemgetter(1))

top_left, _ = min(enumerate([pt[0][0] + pt[0][1] for pt in

ext_contours[0]]), key=operator.itemgetter(1))

bottom_left, _ = min(enumerate([pt[0][0] - pt[0][1] for pt in

ext_contours[0]]), key=operator.itemgetter(1))

top_right, _ = max(enumerate([pt[0][0] - pt[0][1] for pt in

ext_contours[0]]), key=operator.itemgetter(1))

Natural Language Generation:

The Commercial State of the Art in 2020This Entire Article Was Written by Open AI’s GPT2

Learning To Classify Images Without Labels

Becoming a Data Scientist, Data Analyst, Financial Analyst and Research Analyst

## 3.3 Crop and Warp Image

In order to crop the image, we need to know the dimensions of the sudoku. Although sudoku is a square and has equal dimensions, in order to ensure that we dont crop any part of the image we will calculate the height and width.

`width_A = np.sqrt(((bottom_r[0] - bottom_l[0]) ** 2) + ((bottom_r[1] - bottom_l[1]) ** 2))`

width_B = np.sqrt(((top_r[0] - top_l[0]) ** 2) + ((top_r[1] - top_l[1]) ** 2))

width = max(int(width_A), int(width_B))

Similarly, we can calculate height

`height_A = np.sqrt(((top_r[0] - bottom_r[0]) ** 2) + ((top_r[1] - bottom_r[1]) ** 2))`

height_B = np.sqrt(((top_l[0] - bottom_l[0]) ** 2) + ((top_l[1] - bottom_l[1]) ** 2))

height = max(int(height_A), int(height_B))

We need to construct dimensions for the cropped image. Since the index starts from 0, we start from the points are (0, 0) , (width-1,0) ,(width-1, height-1), and (0, height-1). We will then get the grid and warp the image.

dimensions = np.array([[0, 0], [width - 1, 0], [width - 1, height - 1],

[0, height - 1]], dtype="float32")

# Convert to Numpy format

ordered_corners = np.array(ordered_corners, dtype="float32")# calculate the perspective transform matrix and warp

# the perspective to grab the screen

grid = cv2.getPerspectiveTransform(ordered_corners, dimensions)

return cv2.warpPerspective(image, grid, (width, height))

## 3.3 Extract Cells

So we need to process the image again suing adaptive threshold and bitwise_inversion. **Note:** Don’t forget to convert the image to grey scale before processing. I made that mistake. The code seemed simple, didn’t make sense if it had any problem but it kept on showing error. It took 3 hrs for me to realize. During this time, I had my Software Engineer moment when we get a error, don’t understand why after trying everything and then when you realize you feel like breaking your laptop.😅

`# here grid is the cropped image`

grid = cv2.cvtColor(grid, cv2.COLOR_BGR2GRAY) # VERY IMPORTANT

# Adaptive thresholding the cropped grid and inverting it

grid = cv2.bitwise_not(cv2.adaptiveThreshold(grid, 255, cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY, 101, 1))

Extracting every cell/square. Most sudoku are square, but not all of them. For instance, the sudoku used throughout this series is not a square so the cells are not also square. There will extract the celledge_h and college_w using np.shape(grid)

`edge_h = np.shape(grid)[0]`

edge_w = np.shape(grid)[1]

celledge_h = edge_h // 9

celledge_w = np.shape(grid)[1] // 9

We will iterate through the length and width of the cropped and processed image (grid), extract the cells and store them in a temporary grid.

`tempgrid = []`

for i in range(celledge_h, edge_h + 1, celledge_h):

for j in range(celledge_w, edge_w + 1, celledge_w):

rows = grid[i - celledge_h:i]

tempgrid.append([rows[k][j - celledge_w:j] for k in range(len(rows))])

Creating an 9×9 array of the images and converting it into a numpy array, so that it is easier to process.

# Creating the 9X9 grid of images

finalgrid = []

for i in range(0, len(tempgrid) - 8, 9):

finalgrid.append(tempgrid[i:i + 9])# Converting all the cell images to np.array

for i in range(9):

for j in range(9):

finalgrid[i][j] = np.array(finalgrid[i][j])

try:

for i in range(9):

for j in range(9):

os.remove("BoardCells/cell" + str(i) + str(j) + ".jpg")

except:

pass

for i in range(9):

for j in range(9):

cv2.imwrite(str("BoardCells/cell" + str(i) + str(j) + ".jpg"), finalgrid[i][j])return finalgrid