SudokuSolver

The project is hosted here

---

RPReplay_Final1714853595.MP4

How to run and install locally

Navigate to the website folder.
Have node installed and download the dependencies:

npm i

start the website:

npm run dev

Note: The flag --experimental-https is used in dev. This is because safari does not give camera access over http.

Description

This project is an AR sudoku solving application. Making an application like this consists mainly of solving 4 different problems:

• Finding the position of a sudoku in an image
• Predicting the digits already present in the sudoku
• Solving the sudoku
• Displaying the solution

Finding the position of a sudoku

The first step of finding the sudoku is to apply a gaussian blur and an adaptive threshold filter. This is done to enhance edges in the image.

OpenCV.js is then used to find contours, and the largest contour with the shape of a rectangle is assumed to be the sudoku. Once a sudoku has been found, it is projected into a square for further processing.

Predicting the digits already present

To predict the digits, the sudoku is split up into 81 small squares, one for each cell in the sudoku. The background of the cells are removed by setting the pixel values that are under the mean to 0, and empty cells are filtered out by looking at the average pixel value in the cells. The lines used to seperate the cells in the sudoku are removed by clearing the borders of each cell. When removing the background, parts of the digits are also removed, which makes them thinner. Therefore, a dilation kernel is used to increase the thickness of the digits. The result looks something like this:

Once the digits have been processed, they are sent to a CNN trained with a custom dataset containing 4500 digits. All digits in the dataset were processed using the above-mentioned method.

Solving the sudoku

To solve the sudoku, a recursive backtracking algorithm is used. For most practical scenarios this is fast enough, but sudokus can be designed to be resistant against brute force algorithms like this.

Displaying the solution

When a solution is found, it is drawn on a square. A projection matrix is then calculated to project the solution back into the original position in the live camera feed.