I got back to coding after a long absence cause mainly by the final exams. My first project was to implement a recursive Sudoku solver.
I had previously written an iterative Sudoku solver that makes use of the same techniques that people do by ruling out what numbers can fit in a cell untill there is only one possible number that can fir. However, this method fails on harder puzzles where a guess has to be made in order to solve the puzzle.
Brute force algorithms enter here. The Sudoku puzzle lends itself well to the classic recursive brute force algorithm,
The step by step algorithm:
- If puzzle is solved
- If puzzle is not valid
- Find first empty cell : cell that contains 0
- While the cell value is less than 10 and while the puzzle is unsolved
- Increment cell by 1
- If the cell value is greater than 9
- Reset the cell value to 0 : This means that a previous guess was invalid so this ends and the previous cell value is incremented