This project implements a Constraint Satisfaction Problem (CSP) solver for Sudoku puzzles in C# using backtracking search with forward checking.
Each cell in the 9x9 Sudoku grid is a variable, identified by its row and column indices.
The domain of each variable is the set of possible values (1-9) that can be assigned to that cell.
- Each row must contain unique values from 1 to 9.
- Each column must contain unique values from 1 to 9.
- Each 3x3 subgrid must contain unique values from 1 to 9.
The CSP solver implements backtracking search with forward checking using MRV (Minimum Remaining Values) and Degree heuristics for variable selection. The solver picks the variable with the smallest domain size, then the highest degree, then the leftmost column, and finally the topmost row. Domain size is computed by checking the constraints intially and then updated during forward checking and backtracking. Degree is computed as the number of unassigned variables that share a constraint with the current variable.
The solver was tested on 3 puzzles as prescribed in the assignment. The following is the output of that run:
Puzzle 1 Initial State:
..1 | ..2 | ...
..5 | ..6 | .3.
46. | ..5 | ...
------+-------+------
... | 1.4 | ...
6.. | 8.. | 143
... | .9. | 5.8
------+-------+------
8.. | .49 | .5.
1.. | 32. | ...
..9 | ... | 3..
Puzzle 1 solved:
371 | 482 | 695
925 | 716 | 834
468 | 935 | 712
------+-------+------
583 | 164 | 927
692 | 857 | 143
714 | 293 | 568
------+-------+------
837 | 649 | 251
156 | 328 | 479
249 | 571 | 386
First 4 assignments made during solving:
CellAssignment { Row = 4, Col = 5, DomainSize = 1, Degree = 8, Value = 7 }
CellAssignment { Row = 4, Col = 2, DomainSize = 1, Degree = 11, Value = 2 }
CellAssignment { Row = 7, Col = 5, DomainSize = 1, Degree = 10, Value = 8 }
CellAssignment { Row = 4, Col = 4, DomainSize = 1, Degree = 8, Value = 5 }
Time taken to solve: 0.1875
Puzzle 2 Initial State:
..5 | .1. | ...
..2 | ..4 | .3.
1.9 | ... | 2.6
------+-------+------
2.. | .3. | ...
.4. | ... | 7..
5.. | ..7 | ..1
------+-------+------
... | 6.3 | ...
.6. | 1.. | ...
... | .7. | .5.
Puzzle 2 solved:
435 | 216 | 879
682 | 794 | 135
179 | 385 | 246
------+-------+------
217 | 439 | 568
846 | 521 | 793
593 | 867 | 421
------+-------+------
758 | 643 | 912
964 | 152 | 387
321 | 978 | 654
First 4 assignments made during solving:
CellAssignment { Row = 1, Col = 1, DomainSize = 2, Degree = 12, Value = 7 }
CellAssignment { Row = 0, Col = 1, DomainSize = 2, Degree = 12, Value = 3 }
CellAssignment { Row = 2, Col = 1, DomainSize = 1, Degree = 10, Value = 8 }
CellAssignment { Row = 5, Col = 1, DomainSize = 1, Degree = 11, Value = 9 }
Time taken to solve: 0.796875
Puzzle 3 Initial State:
67. | ... | ...
.25 | ... | ...
.9. | 56. | 2..
------+-------+------
3.. | .8. | 9..
... | ... | 8.1
... | 47. | ...
------+-------+------
..8 | 6.. | .9.
... | ... | .1.
1.6 | .5. | .7.
Puzzle 3 solved:
673 | 924 | 185
425 | 138 | 769
891 | 567 | 234
------+-------+------
314 | 286 | 957
267 | 395 | 841
589 | 471 | 326
------+-------+------
748 | 612 | 593
952 | 743 | 618
136 | 859 | 472
First 4 assignments made during solving:
CellAssignment { Row = 1, Col = 0, DomainSize = 2, Degree = 13, Value = 4 }
CellAssignment { Row = 2, Col = 0, DomainSize = 1, Degree = 9, Value = 8 }
CellAssignment { Row = 3, Col = 3, DomainSize = 2, Degree = 13, Value = 1 }
CellAssignment { Row = 8, Col = 1, DomainSize = 2, Degree = 12, Value = 3 }
Time taken to solve: 0.15625