mikemcbride / vue-sudoku

Sudoku solver written in Javascript
https://sudoku.mcbrides.us
MIT License
5 stars 1 forks source link

Optimize Backtracking #9

Closed mikemcbride closed 4 years ago

mikemcbride commented 4 years ago

When we get to a point where we start guessing, we simply find the first unsolved cell and choose the first value in the array of possible values. While this certainly works, it is not optimal. Imagine that the first unsolved cell has 7 values to choose from. You have a 6/7 chance that you chose wrong. Now assume that the next cell only has 2 possible values. It would be far more worth our time to find the cell with the fewest remaining values and start guessing there. This should be relatively easy to implement.