SudokuSolver is a successor from my previous version. The newer version of the software will use OpenCV and Tesseract with the digits trained dataset.
The older software did not always work as intended. The objective is to make this software work flawlessly at any time.
This project has been developed with JDK 17. It is recommended to use this version to avoid any obstacles with the software.
To run SudokuSolver, clone the project via your IDE or code editor and execute "Launch.java".
To obtain the best results, keep the opened browser in focus (IMPORTANT: remove pop ups if it is your first time visiting the website)
The SudokuSolver is tested with https://www.sudoku.com for now.
- Added MRV (Minimum Remaining Values) heuristic
- This improved the average runtime from 2142 milliseconds to 1630 milliseconds
I conducted a performance test of SudokuSolver using www.sudoku.com in evil mode with 100 iterations and an average performance of 1630 milliseconds. It is important to note that the hardware configuration can naturally affect the performance of the solver.
The steps included in this benchmark are:
- Opening the browser and the website
- Screenshot of the website
- Image processing
- OCR
- Solving the Sudoku
- Filling the Sudoku
The backtracking solving algorithm is a brute-force search algorithm that tries all the possible combinations of numbers until a solution is found that satisfies the constraints of the puzzle. Read more about it here
The objective of this algorithm is to identify and extract a Sudoku board from an image.
- Image is converted to grayscale
- Blur filter is applied to the image to reduce noise
- Canny edge detection algorithm to identify the contours and selects the largest contour
- It adds a margin to remove any borderlines
- Finally, the image is extracted by using the coordinates of the bounding rectangle
In order to prepare for optimal contour detection and cell cropping, the board is preprocessed with the following steps:
- The output image is converted to grayscale
- Gaussian blur is applied to the grayscaled image to smooth the image
- Adaptive threshold to convert the image to black and white
To ensure that the digit is in focus for the best OCR results, I had to design a solution that ensured the digit was cropped without any grid or borders included. This was because any non-cropped grid or border was often detected as either a '1' or a '7' which often resulted in incorrect solutions for the sudoku board. My solution was done with the following steps for each cell:
- Convert the cell image to grayscale
- Apply thresholding to create a binary image
- Find contours in the binary image
- Find the contour with the largest area (assumed to be the contour of the digit in the cell)
- Find the bounding rectangle of the largest contour
- Extract the region within the bounding rectangle
The objective of this algorithm is to perform OCR to identify the digit. The training dataset applied for this is specified for digit training.
This software is developed and designed by Hassan K