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 Strategize Next Page

How can we defeat these horrible Samurai? Let's take a close look at how our solver works.

This image is taken after the first backtracking. That means that every cell that has a value filled in had either only one possible value, or was guessed at...



But... look at that one cell highlighted in red. Right now it can take on the values 3 and 7... but, 3 can't appear in any other cell within its 3x3 square. So, we (as the humans we are) can immediately deduce that 3 must be the only value that can be in that square; as there's no where else it could possibly go.

Why doesn't our solver see that?

The answer is because we (and when I say 'we' I mean 'I') did something stupid. When we set up the constraints for this problem, we said that the value in a cell cannot be equal to any of the other ~20 cells surrounding it. In so doing, we actually threw out a bit of information: not only are the values not equal, but in a given row, column, or square, the values are 'unique', a fun way of saying 'the values 1-9 appear in every grouping'. This implies that if a value can be generated by only one cell in a group without violating a not equal constraint, then that cell must have that value.

Seems small doesn't it? Let's see what the effect is.

Previous Page Strategize Next Page