Sudoku using Backtracking

Algorithm

Summary: In this post, we will learn What Sudoku is and how to solve the sudoku puzzle using the backtracking algorithm in C, C++, and Java.

What is Sudoku?

Sudoku is a logic-based, combinatorial number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid contain all of the digits from 1 to 9.

Initially, we are given a partially-filled grid like the following:

sudoku uncomplete

We need to fill the blanks cells such that the same number should not appear twice in the corresponding row + column and in any of the nine 3×3 subregions/boxes of the grid.

sudoku complete

Sudoku Solution using Backtracking Algorithm

We can easily solve sudoku using the backtracking approach as follows:

  1. We will fill the cells column vise.
  2. For every cell, we will check if it is empty (or has 0) or not.
  3. If the cell is empty, we will then check which number from 1 to 9 is valid for the particular cell and update the cell accordingly.
  4. If the current cell is not empty, we will move to the next cell of the same column or first row of the next column if at the last cell of the column.
  5. If none of the numbers from 1 to 9 is valid for the current cell, we will go back to the last updated cell and try with another valid value (i.e. backtrack).
  6. To achieve backtracking, we will return to the last recursive call by returning false check with the next value of the iteration of ‘for loop’. We again proceed to the next cell after updating the last cell with another valid value.

To implement backtracking, we will use recursion with the following base condition:

//if reached the 10th column (passed 9th)
//sudoku filling completed, so display board
if(col == 9){
    displayBoard();
    return true;
 }

Here is the full implementation of the above discussed algorithm in Java and C++.

Java

class Sudoko{
  int board[][];
 
  Sudoko(int board[][]){
    this.board = board;
  }
    
  public boolean solve(int row, int col){
    //if reached the 10th column (passed 9th)
    //sudoku filling completed, so display board
    if(col == 9){
      displayBoard();
      return true;
    }
    
    //If cell already has a number
    if(board[row][col] != 0){
      if(row == 8) return solve(0,col+1);
      else return solve(row+1,col);
    }
        
    //If cell is blank
    for(int i=1; i<=9; i++){ 
      //Place a number in the cell       
      board[row][col] = i;
      //check if the placed number is valid
      if(isValid(row,col)){
        //Yes
        //If reached at last row then move to
        //starting of next column
        if(row == 8){
          if(solve(0,col+1))
            return true;
          }
        else{
          //Next cell of the same column
          if(solve(row+1,col))
            return true;
        }      
      }      
    }
    
    //Reset and Backtrack
    board[row][col] = 0;
    return false;
            
    }
    
    //Function to display board
    private void displayBoard(){
      for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
          System.out.print(board[i][j]+" ");
        }
        System.out.println();
      }
        
      System.out.println("\n\n");
    }
    
    //Function to check if the current placement in
    //board[row][column] is valid or not
    private boolean isValid(int row, int column){
      //Checking he column (horizontal)
      for(int i=0; i<9; i++){
        if((board[row][i] == board[row][column]) && (i != column))
          return false;
      }
      //Checking the row (vertical)
      for(int i=0; i<9; i++){
        if((board[i][column] == board[row][column]) && (i != row))
          return false;
      }
      //Computing starting point of the current Grid
      int sr = (row/3)*3;
      int sc = (column/3)*3;
      //Checking the grid (3x3)
      for(int i=sr; i<sr+3; i++){
        for(int j=sc; j<sc+3; j++){
          if(board[row][column] == board[i][j] && (row != i) && (column != j))
            return false;
        }
      } 
      return true;
    }
}
 
public class Main
{
	public static void main(String[] args) {
	    
    int board[][] =  {{5, 3, 0, 0, 7, 0, 0, 0, 0},  
                      {6, 0, 0, 1, 9, 5, 0, 0, 0}, 
                      {0, 9, 8, 0, 0, 0, 0, 6, 0}, 
                      {8, 0, 0, 0, 6, 0, 0, 0, 3}, 
                      {4, 0, 0, 8, 0, 3, 0, 0, 1}, 
                      {7, 0, 0, 0, 2, 0, 0, 0, 6}, 
                      {0, 6, 0, 0, 0, 0, 2, 8, 0}, 
                      {0, 0, 0, 4, 1, 9, 0, 0, 5}, 
                      {0, 0, 0, 0, 8, 0, 0, 7, 9}}; 
                         
		Sudoko sudoko = new Sudoko(board);
		sudoko.solve(0,0);
	}
}

C++

#include <iostream>
 
using namespace std;
 
int board[9][9] =  {{5, 3, 0, 0, 7, 0, 0, 0, 0},  
                  {6, 0, 0, 1, 9, 5, 0, 0, 0}, 
                  {0, 9, 8, 0, 0, 0, 0, 6, 0}, 
                  {8, 0, 0, 0, 6, 0, 0, 0, 3}, 
                  {4, 0, 0, 8, 0, 3, 0, 0, 1}, 
                  {7, 0, 0, 0, 2, 0, 0, 0, 6}, 
                  {0, 6, 0, 0, 0, 0, 2, 8, 0}, 
                  {0, 0, 0, 4, 1, 9, 0, 0, 5}, 
                  {0, 0, 0, 0, 8, 0, 0, 7, 9}}; 
 
class Sudoko{
 
public:
    
  bool solve(int row, int col){
    //if reached the 10th column (passed 9th)
    //sudoku filling completed, so display board
    if(col == 9){
      displayBoard();
      return true;
    }
    
    //If cell already has a number
    if(board[row][col] != 0){
      if(row == 8) return solve(0,col+1);
      else return solve(row+1,col);
    }
        
    //If cell is blank
    for(int i=1; i<=9; i++){ 
      //Place a number in the cell       
      board[row][col] = i;
      //check if the placed number is valid
      if(isValid(row,col)){
        //Yes
        //If reached at last row then move to
        //starting of next column
        if(row == 8){
          if(solve(0,col+1))
            return true;
          }
        else{
          //Next cell of the same column
          if(solve(row+1,col))
            return true;
        }      
      }      
    }
    
    //Reset and Backtrack
    board[row][col] = 0;
    return false;
            
    }
    
    //Function to display board
    void displayBoard(){
      for(int i=0; i<9; i++){
        for(int j=0; j<9; j++){
          cout << board[i][j] << " ";
        }
        cout << "\n";
      }
        
      cout << "\n\n";
    }
    
    //Function to check if the current placement in
    //board[row][column] is valid or not
    bool isValid(int row, int column){
      //Checking he column (horizontal)
      for(int i=0; i<9; i++){
        if((board[row][i] == board[row][column]) && (i != column))
          return false;
      }
      //Checking the row (vertical)
      for(int i=0; i<9; i++){
        if((board[i][column] == board[row][column]) && (i != row))
          return false;
      }
      //Computing starting point of the current Grid
      int sr = (row/3)*3;
      int sc = (column/3)*3;
      //Checking the grid (3x3)
      for(int i=sr; i<sr+3; i++){
        for(int j=sc; j<sc+3; j++){
          if(board[row][column] == board[i][j] && (row != i) && (column != j))
            return false;
        }
      } 
      return true;
    }
};
 
int main()
{
    Sudoko sudoko;
    sudoko.solve(0,0);
 
    return 0;
}

Output:

output for sudoku program

In this tutorial, we learned to solve Sudoku Puzzle programmatically using the backtracking algorithm in C++ and Java programming languages.

Leave a Reply

Your email address will not be published. Required fields are marked *