Sub-Teams‎ > ‎Programming‎ > ‎

Sudoku Solver

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.

Approach

We 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 Routines

There 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

Solution

To 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!