Open-CV Based Sudoku Solver Powered By Rust

An image-based sudoku solver with rust batteries

Photo by Ant Rozetsky on Unsplash

Project Motivation

Okay so one day browsing through Reddit, I came across a project, It was a sudoku solver using video cam stream. The project was cool, but there was the only thing I didn’t like: it used to crop the sudoku image and give a solved sudoku image solution.

So I thought why not project back the solution to the original image to make it look like it's solved in the original image?

Pretty cool right?!

About Project

The project is simple, take the sudoku image, solve it and project back the solution to the original image, thats all!!

Well, that was my initial plan, but the execution is another thing.

Brief project technology description :

• Get the sudoku block in the image — Python OPEN CV
• Crop the sudoku image and change perspective — Python OPEN CV
• Extract the digits in some ordered manner — Python KNN Model
• Solve the sudoku — Using Rust Sudoku Solver
• Project back the solution into the original image — Python OPEN CV

Well we can solve the sudoku using Python but for some reason, I wanted to try adding Rust to python, also its faster than python in solving the sudoku.

If you find it interesting, let's start!!

Crop & Change Perspective

After this section, we will be converting the full image to cropped sudoku image.

Initial Image:

Okay so basic logic is

1. Get the biggest box in the image as it will be most probably the sudoku box.
2. Next is to draw lines along the sudoku box edges.
3. Find the intersection points of these lines.
4. Use the intersection points to change the perspective of the image and get the cropped sudoku.

Okay, so let's see each step one by one!

Getting the biggest box:

Let's understand the code!

First of all, contour is basically any closed shape

we will be using opencv library, the steps are:

• Converting image to GRAY
• Using adaptiveThreshold to convert each pixel of the image to either black or pure white.
• Opencv has a function findContours it returns the contours(closed shape)
• Going through Each contour and getting the max area contour.

After this, we will be having the biggest contour which most probably is the sudoku box.

As this just gives the outline of the shape, we can’t use it to get the sudoku box, we need the four corner points to change perspective.

Hence we will be first drawing this contour on a blank image and then draw straight lines on this shape, it will give us four lines which will be later used to get the four corner points.

After this, we will have lines along the sudoku sides but the thing is, there are multiple lines along a single side because the Houghlines uses roughly inline points to draw a line and as our image is not very clear nor is the correct perspective hence what we get is multiple lines along a single side.

So what we will be doing is we will eliminate all lines which are close to each other, but leave one hence we will be left with 4 lines for 4 sides.

So now we have 4 lines, what’s left is to get the intersection points of these lines.

Well as our lines are not parallel hence we will be getting 6 points of intersection. To solve this we will be using the slope of lines, we will divide the lines into 2 categories, horizontal and vertical. And this way we will get only 4 points.

Note: The lines are not horizontal and vertical, but are just 2 categories.

for (rho,theta) in createhor:
        for (rho1,theta1) in createver:
            if (rho,theta)!=(rho1,theta1):
                a=[[np.cos(theta),np.sin(theta)],[np.cos(theta1),np.sin(theta1)]]
                b=[rho,rho1]
                cor=np.linalg.solve(a,b)
                if list(cor) not in points:
                    points.append(list(cor))

Now we have 4 corner points, it’s time to do the magic and get the sudoku image.

Nothing fancy, we will be using the warpPerspective to change the perspective and get the image.

Final output:

Extract Digits from Sudoku Image

This section will be focused on extracting the digits from sudoku image.

So first is some eroding and dilating to remove the noise.

Next is to get the contour of digits, and drawing the on a new blank image. After that, it's just drawing the divider lines.

After this, we will get

A clean sudoku image with no noise.

Next is simple, just iterating through each box and predicting the numbers. The first approach which failed very very miserably was to use a CNN model and training it to predict the numbers. But for some reason, it was only predicting 6 no matter what the input was.

After some experimenting, I went ahead with the KNN Model.

The first problem was to create the dataset, Tried kaggle but apparently there are no datasets for simple plain numbers. So I created a script which first writes the digits on an image, adds some Noise and blur to make it realistic and then crop it.

Then I used another good library Augmentor. It uses the present images and adds random tilts, rotations etc. Hence what I got was 10k images for each number. Pretty cool!! At least for me, I was not able to sleep after doing that masterpiece stuff. Okay after we are done of thinking about it, let's move to train the model.

Next was easy, just use this model to predict the numbers and creating a new image of a sudoku.

After everything, what we have is:

Solve Sudoku

We will be solving sudoku using Rust in this section.

After our last section, we have numbers in sudoku image, what's left is to code a sudoku solver, in rust and thankfully we can export it into a library which can be imported in python.

There is a library sudoku which provides a good sudoku solver, so I used it to create a function and wrote Python bindings to import in python, another masterpiece moment lol.

After this solving the sudoku and creating a solution mask was left.

And the final solution looked like.

Great!! Let's move to the next part.

Project the Solution To Original Image

The final section, it will be focusing on projecting the solution to the original image.

Once we have solution mapped on a black image, just doing a bitwise not and was enough to remove the black part of the image, and as we had the initial points, changing back the perspective, is also easy

M = cv2.getPerspectiveTransform(pts2,pts1)
    
    img = cv2.warpPerspective(sudoku_image,M,(original.shape[1],original.shape[0]))
    img = cv2.bitwise_not(img)
    img = cv2.bitwise_and(img,original)

That's all!! The final image is

Source Code

You can find whole source code at!!

pr4k/sudoku-solver

Thanks for reading!!