On an extra-long episode on 0612 TV this week, we built our very own brute force Sudoku solver! By using recursion, we were able to write code that can brute-force any sudoku puzzle. It is even able to find answers to ambiguous puzzles, such as an empty board.
To download the code written in the video, which comes with the two sample puzzles, check out this Google Drive folder: https://drive.google.com/open?id=0B2Ia5aQpQ8CndnRReS1xUy04QW8
The following are the functions written in the code:
Prepares the board, then calls solve() before displaying the result.
The main workhorse of our program – This function tries to solve for all “obvious” solutions first by making a call to fillAllObvious(). If required, it fills in a cell by guessing, before making a recursive call to itself. solve() returns true if the puzzle has been solved, and false if it has encountered a contradiction, which indicates a wrong guess.
This function loops through all the cells on the board. For empty cells, it tries to find what numbers are possible at the cell by using getPossibilities(). If only one number is possible, the number is filled onto the board. This process is repeated until no more cells can be filled by the function.
If at any point of time we encounter a cell in which no numbers are possible, it indicates that there has been an incorrect value inserted somewhere. As such, it raises an exception.
This function checks which values are possible at a particular cell as indicated by “i” and “j”. By starting off with a set, this function works by taking away values it encounters while looping through the row “i” and column “j”, in addition to the square associated with (i,j). The result is cast to a list and returned
Loops through all the cells of the board and displays their values.
Checks every cell on the board. If no more empty cells (indicated by dots) are encountered, the function returns true. Otherwise, it returns false.
For more information, please refer to the video! In it, I walk through building the Sudoku solver step-by-step. That’s it for now! If you like what you see and are feeling generous, you are very welcome to shoot me a donation for my work. I would greatly appreciate that!