Sudoku is played on a grid of 9 x 9 spaces. Within the rows and columns are 9 “squares” (made up of 3 x 3 spaces). Each row, column and square (9 spaces each) needs to be filled out with the numbers 1-9, without repeating any numbers within the row, column or square.
We want to avoid using the Naive Approach (try out every possible value to acquire a solution) due to having to possibly run 981 possibilities due to having a 9x9 grid with 9 possible values within in cell.
We want to use a backtracking approach to help solve this problem. The approach is as such:
- Pick an empty cell
- Try all numbers
- Find one that works
- If 3 worked, then repeat process for rest of board
- Backtrack as soon as a solution cannot be completed
The goal is to complete one cell at a time and recursively checking that the solutions work until you get to one that does work. This approach is a lot faster than the Naive Approach due to not having to compute 981 calculations.
For each of the steps listed, we should be able to create an function/file dedicated for each.
- Create a function to find the empty cells
- Function to try/iterate through all numbers
- Check current solution/Check if the number we put in is valid
- Reset the value when a solution is not correct