Yesterdays post was about backtracking and to milk as much as possible from this topic I thought I would demonstrate another example of how this can work. I failed to do a Sudoku from the newspaper this morning and thought – hang on, could I use backtracking to solve it for me.
How Sudoku Works
Sudoku is a good candidate to be solved via backtracking as before we write a number into a cell, we are able to check if it is currently valid or not (that it meets all the required constraints). A Sudoku cell has 3 constraints.
- Each row must have no repeating numbers
- Each column must have no repeating numbers
- Each 3*3 Square must have no repeating numbers
So to write a backtracking solution to this problem we would need to do the following;
- Write a function that checks if the position we are attempting to write to is safe or not (check the constraints listed above)
- Place a number if the constraints are met and recursively check if this leads to a solution or not. If it doesn’t try the next number until a solution is met
C# Implementation
The code is at SudokuSolver(github.com)
Checking Constraints
The method used to check the constraints is IsValueOK – this checks all of the 3 constraints mentioned previously a separate method for each and validates they are all true (in which case the number can be placed in the proposed cell).
The recursive function is named SolveSudoku – validating if a number can be placed and then recursively trying the next numbers until one can be placed.
The PrintResult method prints the grid to the console.
In the Main method there is a Sudoku taken from a puzzle online in the form of a multi-dimensional array.
Looks like I shall never be thwarted by the local paper again!