Skip to content

🌲 A augmented reality sudoku solver using random forest classifier and backtracking algorithm

License

Notifications You must be signed in to change notification settings

YashIndane/AR-Sudoku-Solver

Repository files navigation

AR-Sudoku-Solver

A augmented reality sudoku solver using random forest classifier and backtracking algorithm

Link to demo -> demo

sudoku-g

Description

1.Building the dataset

For building the dataset the same program is used which is used for capturing the square grids during solving.

Installation

$ pip install opencv-python

By this method we are capturing 23 by 23 size grayscale images. There are 529 features, upon which the classifier will be trained.

Sample training images - 12 11 8

Total 1600 images of numbers from 0-9 are then fed to the dataset generator program which generates the required .csv file. The generated file with 530 coloumns is then used by model builder , which makes a random forest classifier. Accurracy acheived on test data is around 98%.

What is Random Forest Classification?

a forest2

A Random Forest Classifier is a set of decision trees which randomly select subset of training set. The final decision comes from the aggregation of votes from all the trees. It has been implemented with the scikit-learn library.

Note-

(optional) For shuffling up the csv file we can do this after reading the file-

data = data.sample(frac=1).reset_index(drop=True)

Grabbing the digits from the grid

Countours are been used to detect polygons present in the live video. They later are been filtered out on the basis of countour-area and no. of sides.

detection1

The extracted digits are then predicted using our pre-trained ML model , and the whole numbers are sent to the sudoku solver which solves it with efficient backtracking algorithm.

Solving

Backtracking algorithm - Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time.

ss1

One of the fastest solves in 16 msecs!

fastest_solve

Sudoku Solving Vizualizer

Resources

For getting the sudoku puzzles go to - http://www.websudoku.com/

For getting solution of puzzles go to - https://sudokusolver.net/

About

🌲 A augmented reality sudoku solver using random forest classifier and backtracking algorithm

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages