(GitHub Repo: https://github.com/alulema/SudokuSolverNet)
I was revisiting a couple of basic AI concepts: Depth First Search and Constraint Propagation, and I found a very good explanation by Professor Peter Norvig (Solving Every Sudoku Puzzle), I just want to add a couple of simple explanations for a better understanding of the concepts.
Constraint Propagation
This technique is used to reduce the search space and make the problem easier to solve. In Sudoku domain, it means following the game rules and define the possible solutions to assign to each box in the table.
Elimination Strategy.
The idea is to reduce the possible values to be assigned to a box. Just let me redefine the concepts for a better understanding.
Box.
We have 81 boxes in the puzzle
Unit.
Each box will be into 3 different units, each unit contains 9 boxes, each of them have different values, from 1 to 9.
Peer.
Each peer contains 21 boxes, and the box’s value cannot be in any other element of this peer.
Considering this 3 concepts, the puzzle should be seen in this way:
One-Choice Strategy.
This strategy consists in seen the only choice to be accepted by a box in a unit. This helps to reduce the options in Elimination.
In the following image, we can see that number 4 can be assigned to only one cell.
First Depth Search
This strategy will be applied after Constraint-Propagation, and considering it didn’t find a solution. It will be more CPU demanding, but it is the actually a basic approach; it doesn’t prune any options at all. The only check it makes is that all the assigned values so far are consistent with each other.
This strategy can be described as a tree, where we try possible solutions by assigning the possible options to a box and checking one by one if it solves the puzzle re-applying Constraint-Propagation again with this testing value.
By using First Depth Search, this tree is navigated in the following order:
A-B-D-E-I-J-C-F-G-H-K-L
You can think each leaf of this tree as:
“Will it solve the puzzle?”
In sudoku, we are going to start with the box with less options to be solved.
For example, in this unit, we can start with box with 56 as the probable choices, then we try to solve the puzzle with 5, if it is not solved we try with 6, and so on.
C# Solution
Professor Norvig implements the algoritms in Python, I’ve done this in C# as I consider C# is a little bit more clear than Python to understand how it works (it is just my opinion, maybe you find Python more clear).
