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 Better Brute Force Next Page



Well. That's not as bad. In fact, it is at least a few trillion times faster then the last solution. But it is still debatable as to whether or not it will finish in our life times.

There's one small improvement I want to make before moving on though. Take a look at:



Does anything seem wrong with it?

It has 2 3's in a 9x9 square, and is part of a constraint violation. I think that it seems kind of silly to try assigning a 3 to the highlighted cell, when it is blatantly obvious that that would violate the constraints of the problem. We could probably cut the number of states we need to explore in half by limiting the values we try for a cell to only those that won't violate current constraints.

This has the effect that, rather than violating constraints being the sign of 'its time to backtrack', we'll generate cells which have no valid values which can be assigned. That is important to remember in the next section.

Previous Page Better Brute Force Next Page