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 How to Think About It Next Page

Another way to think about this is that a number in a cell cannot be equal to any other number in its row, column, or square. This is called a Constraint.

For each cell we define a Variable which has the values that the cell can take. We then define all the constraints that affect that variable. For example, constraints may say that cell C[1,1] != C[2,1], C[1,1] != C[1,2] and so on. All told there are 24 constraints for each cell, and 81 cells, for a total of 1,944 constraints.

If you can find the values for each cell such that no constraint is violated, then you have solved the sudoku puzzle. This set of numbers is called a Satisfying Assignment, and the problem of finding a satisfying assignment is the Constraint Satisfaction Problem.

We are going to use methods for solving Constraint Satisfaction Problems to solve Sudoku.

Previous Page How to Think About It Next Page