A Sudoku is a puzzle on a 9x9 grid which is filled in with the numbers 1-9. Initially, some of the grid is empty, and the objective is to fill in the empty cells using the numbers 1-9 such that: - each row contains the numbers 1-9, once each
- each column contains the numbers 1-9, once each
- each of the 3x3 sub-squares in the grid contains the numbers 1-9, once each
Each valid puzzle has only one unique solution. ## ApproachWe use a recursive approach when solving a Sudoku using software. We try each number 1-9 in each empty cell until a solution is found. In order to optimize this type of search, we eliminate numbers already in the row, column, and sub-square to determine the list of valid possible number for each cell. ## Main Useful RoutinesThere are two main useful routines that aid solving of the puzzle - getNextEmptyCell - determine the row and column of the next empty cell
- getGuesses - determine the list of possible guesses for this cell, eliminating numbers already in the row, col, and sub-square.
Once these routines are constructed, the solution is straightforward ## SolutionTo solve the puzzle, create a solve() routine that returns a boolean and follow the steps: - get the next empty cell. If there isn't an empty cell, then the solution is found, so print it, and return true;
- get all of the possible guesses at the empty cell.
- for each of the possible guesses, fill in the cell with the guess, and then call the solve routine again (recursion)
- if the solution is found, then stop and return true;
- if no solution is found after trying each value, then clear the cell again and return false;
This recursive solution will quickly find the solution to the Sudoku. An example java solution can be found here, but you should not need it! |

Sub-Teams > Programming >