- Introduction
- Sudoku Explained
- How to Think About It
- Getting Started
- A First Approach-
Brute Force - Brute Force in Action
- Improving on Brute Force
- Better Brute Force
- Backtracking Search
- Backtracking with MRV
- Attack of the Samurai
- Strategize
- Backtracking MRV with
Unique Constraint - Backtracking MRV with
Unique Constraint part 2 - Conclusion
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.