1. Introduction
  2. Sudoku Explained
  3. How to Think About It
  4. Getting Started
  5. A First Approach-
    Brute Force

  6. Brute Force in Action
  7. Improving on Brute Force
  8. Better Brute Force
  9. Backtracking Search
  10. Backtracking with MRV
  11. Attack of the Samurai
  12. Strategize
  13. Backtracking MRV with
    Unique Constraint

  14. Backtracking MRV with
    Unique Constraint part 2

  15. Conclusion
Previous Page Backtracking Search Next Page



This modified version of the Brute Force approach is called Backtracking Search. And while it is near enough infinitely faster then normal Brute Force, it is still too slow for our needs. How can we improve it?

One cue we can take from Humans. When a human encounters a cell which can take on only one value without violating its constraints, it will usually choose that cell to expand, utilizing its only value. If the human has to guess, it will usually pick the cell with the fewest values to try. Similarly, if the human spots a cell which has no possible values, the human knows that it made a horrendous mistake, and will start backtracking.

Right now, we don't do any of that. If a set of assignments in the top row causes a cell in the bottom row to have no valid values, we go through the entire search tree above it before getting to the point where the original conflict can be solved. To illustrate:



We also spend alot of time with incomplete information; in the above, we can rule out 2 as a choice in any of the cells in the first column if we know that the bottom cell must be a 2. This decreases how many random things we have to try by a lot. So, we should try and use this idea.

Thankfully we can apply this human-inspired logic to our solver. This is called the Minimum Remaining Values Heuristic. In order to use this heuristic, we must determine all the possible values every single cell can hold. For a human this is a rather tedious task; but thankfully computers don't grow bored. Let's see it in action.

Previous Page Backtracking Search Next Page