Sudoku Solver
Below is a simple solution for solving any 9x9 sudoku puzzle. The rules of sudoku are as follows:
1. Each row and column must contain the digits 1-9 exactly once.
2. Each 3x3 sub-grid must contain the digits 1-9 exactly once.
Pretty easy rules, but surprisingly complex solution in practice. When a person solves a sudoku puzzle, each empty cell is scanned and the two rules are applied. While that's certainly possible to emulate in code, that's not the most straightforward solution.
One approach is to use brute force. Generate every single possible combination of numbers and test each of them until one works. However, the minimum number of given cells required to make a puzzle solvable is 17, meaning there could be up to 64 empty cells! If one were to brute force the solution, there would be 9^64 solutions to test.
So how do we do better? For starters, we don't need to generate possible values for all 64 cells at once. Maybe we've already made an error before we get to the last cell. Let's try a more sequential approach.
Starting with an example problem:
One approach is to use brute force. Generate every single possible combination of numbers and test each of them until one works. However, the minimum number of given cells required to make a puzzle solvable is 17, meaning there could be up to 64 empty cells! If one were to brute force the solution, there would be 9^64 solutions to test.
So how do we do better? For starters, we don't need to generate possible values for all 64 cells at once. Maybe we've already made an error before we get to the last cell. Let's try a more sequential approach.
Starting with an example problem:
Classic Fizzbuzz
We let all empty cells be 0s in this case. The first empty cell is to the right of the 3. If we insert a 1 there, everything is fine, no problems. Since we have evidence that that is a bad guess, we can move onto the next cell to the right. If we again try to place a 1 there, we see that there are conflicts with the preceding 1 and also the 1 that's on the second row. Logically, we can try 2 instead, etc.
That's all good and fine, but what if we go all the way to 9 and it still doesn't work?? Well, it means that one of our previous entries was already wrong. So, we backtrack. That's the foundation for this algorithm.
We can list out the logic a little bit more explicitly here:
A lot of the code ends up being helper functions to test if the current board assignment is legal and to find empty cells, so we'll skip that here. However, the full solution can be found at Github, which is linked under the title.
The main loop of the code contains the implementation of the algorithm, shown below.
That's all good and fine, but what if we go all the way to 9 and it still doesn't work?? Well, it means that one of our previous entries was already wrong. So, we backtrack. That's the foundation for this algorithm.
We can list out the logic a little bit more explicitly here:
- Find all the empty cells, which we'll call holes.
- Go the first hole and fill it with 1.
- Test to see if that's a legal entry.
- If it is legal, move on to the next hole.
- If it is not legal, increase the value (e.g. to 2).
- If the value is now greater than 9, an error has been made. Reset the current hole back to 0 and go back to the previous hole.
- Increase the value of the (now) current hole.
A lot of the code ends up being helper functions to test if the current board assignment is legal and to find empty cells, so we'll skip that here. However, the full solution can be found at Github, which is linked under the title.
The main loop of the code contains the implementation of the algorithm, shown below.