search

anhminhtran235 / real_time_sudoku_solver

An application that connects to Computer Webcam and solve Sudoku in Real Time (Python, OpenCV and Keras)
13 stars 10 forks source link

Reference of Sudoku Solver algorithim. #1

Closed snehitvaddi closed 4 years ago

snehitvaddi commented 4 years ago

Hey Tran, could you share resources from where you learned and implemented the Best First Search approach.

anhminhtran235 commented 4 years ago

Hi, the most usual way people solve Sudoku is using Backtracking. Check out a few resources explaining this approach:

1/ https://www.youtube.com/watch?v=JzONv5kaPJM&t=67s 2/ https://www.youtube.com/watch?v=eqUwSA0xI-s

I optimized this Backtracking algorithm, by picking the "best" cell to fill next instead of picking the cell from top to bottom, left to right. "Best" here is determined by the number of possibilities that a cell can have. For example, if the row containing that cell has already had number 1 2 3, the column's had 4 5 6, and the 3x3 block's had 7, then there are only 2 possibilities left: 8 and 9. This looks like a pretty good cell to pick.

Since I pick the "Best" cell, I call it "Best First Search". I saw this idea on StackOverflow in a comment, but I implemented it totally on my own.

I have another project called Sudoku Solver Visualizer. The code is in my Github (It's quite messy). You can also see the animation of each algorithm here: https://anhminhtran235.github.io/sudoku-solver-visualizer/

snehitvaddi commented 4 years ago

@anhminhtran235 Your code is clear and fantastic. Thank you for the reference. and I am sorry for using your code and uploading output to my YouTube channel!! Btw, I had taken down my YouTube video.

anhminhtran235 commented 4 years ago

@snehitvaddi Thanks for the compliment bro. I'm glad you found it helpful. And no worry about the Youtube video :)