Backtracking to solve a sudoku puzzle

The applet on this page solves a sudoku puzzle by recursion and backtracking.

The algorithm does not use a clever stragtegy to solve the puzzle. It picks a valid number for each cell and backtracks if this choice leads to a conflict later on:

• When solve is called for the tenth row, the puzzle is solved.
  All of the recursive calls are terminated at once by throwing an exception.
• Find the lowest number which is valid for the current cell
• Write it into the cell
• Delegate work on the next cell to a recursive call to solve
• Whenever the recursion returns, the puzzle cannot be solved for the selected number.
  The next valid number is written into the cell and the recursion for the next cell is called.
  If there are no more valid numbers, the cell is cleared and backtracking starts.

The applet is slowed down by calls to sleep( 1000 ) to give observers a chance to see how the algorithm is working...

This is a fairly typical applet. The server serves the class file, and the code runs in the browser

Download source

The german version of this page shows a slightly different implementation of the algorithm

/*********************************************************/
/*                                                       */
/* An applet to demonstrate recursion and backtracking   */
/* ===================================================   */
/*                                                       */
/* V0.3   18-MAR-2007  P. Tellenbach   www.heimetli.ch   */
/*                                                       */
/*********************************************************/
import java.applet.* ;
import java.awt.* ;

/**
 * Solves a sudoku puzzle by recursion and backtracking
 */
public class SimplifiedSudoku extends Applet implements Runnable
{
   /** The model */
   protected int model[][] ;

   /** The view */
   protected Button view[][] ;

   /** Creates the model and sets up the initial situation */
   protected void createModel()
   {
      model = new int[9][9] ;

      // Clear all cells
      for( int row = 0; row < 9; row++ )
         for( int col = 0; col < 9; col++ )
            model[row][col] = 0 ;

      // Create the initial situation
      model[0][0] = 9 ;
      model[0][4] = 2 ;
      model[0][6] = 7 ;
      model[0][7] = 5 ;

      model[1][0] = 6 ;
      model[1][4] = 5 ;
      model[1][7] = 4 ;

      model[2][1] = 2 ;
      model[2][3] = 4 ;
      model[2][7] = 1 ;

      model[3][0] = 2 ;
      model[3][2] = 8 ;

      model[4][1] = 7 ;
      model[4][3] = 5 ;
      model[4][5] = 9 ;
      model[4][7] = 6 ;

      model[5][6] = 4 ;
      model[5][8] = 1 ;

      model[6][1] = 1 ;
      model[6][5] = 5 ;
      model[6][7] = 8 ;

      model[7][1] = 9 ;
      model[7][4] = 7 ;
      model[7][8] = 4 ;

      model[8][1] = 8 ;
      model[8][2] = 2 ;
      model[8][4] = 4 ;
      model[8][8] = 6 ;
   }

   /** Creates an empty view */
   protected void createView()
   {
      setLayout( new GridLayout(9,9) ) ;

      view = new Button[9][9] ;

      // Create an empty view
      for( int row = 0; row < 9; row++ )
         for( int col = 0; col < 9; col++ )
         {
            view[row][col]  = new Button() ;
            add( view[row][col] ) ;
         }
   }

   /** Updates the view from the model */
   protected void updateView()
   {
      for( int row = 0; row < 9; row++ )
         for( int col = 0; col < 9; col++ )
            if( model[row][col] != 0 )
               view[row][col].setLabel( String.valueOf(model[row][col]) ) ;
            else
               view[row][col].setLabel( "" ) ;
   }

   /** This method is called by the browser when the applet is loaded */
   public void init()
   {
      createModel() ;
      createView() ;
      updateView() ;
   }

   /** Checks if num is an acceptable value for the given row */
   protected boolean checkRow( int row, int num )
   {
      for( int col = 0; col < 9; col++ )
         if( model[row][col] == num )
            return false ;

      return true ;
   }

   /** Checks if num is an acceptable value for the given column */
   protected boolean checkCol( int col, int num )
   {
      for( int row = 0; row < 9; row++ )
         if( model[row][col] == num )
            return false ;

      return true ;
   }

   /** Checks if num is an acceptable value for the box around row and col */
   protected boolean checkBox( int row, int col, int num )
   {
      row = (row / 3) * 3 ;
      col = (col / 3) * 3 ;

      for( int r = 0; r < 3; r++ )
         for( int c = 0; c < 3; c++ )
         if( model[row+r][col+c] == num )
            return false ;

      return true ;
   }

   /** This method is called by the browser to start the applet */
   public void start()
   {
      // This statement will start the method 'run' to in a new thread
      (new Thread(this)).start() ;
   }

   /** The active part begins here */
   public void run()
   {
      try
      {
         // Let the observers see the initial position
         Thread.sleep( 1000 ) ;

         // Start to solve the puzzle in the left upper corner
         solve( 0, 0 ) ;
      }
      catch( Exception e )
      {
      }
   }

   /** Recursive function to find a valid number for one single cell */
   public void solve( int row, int col ) throws Exception
   {
      // Throw an exception to stop the process if the puzzle is solved
      if( row > 8 )
         throw new Exception( "Solution found" ) ;

      // If the cell is not empty, continue with the next cell
      if( model[row][col] != 0 )
         next( row, col ) ;
      else
      {
         // Find a valid number for the empty cell
         for( int num = 1; num < 10; num++ )
         {
            if( checkRow(row,num) && checkCol(col,num) && checkBox(row,col,num) )
            {
               model[row][col] = num ;
               updateView() ;

               // Let the observer see it
               Thread.sleep( 1000 ) ;

               // Delegate work on the next cell to a recursive call
               next( row, col ) ;
            }
         }

         // No valid number was found, clean up and return to caller
         model[row][col] = 0 ;
         updateView() ;
      }
   }

   /** Calls solve for the next cell */
   public void next( int row, int col ) throws Exception
   {
      if( col < 8 )
         solve( row, col + 1 ) ;
      else
         solve( row + 1, 0 ) ;
   }
}