Solving Sudoku using backtracking | faceprep

Program to solve Sudoku using backtracking is discussed here. 

Given a matrix of 9*9 incomplete sudoku (unassigned places are represented by 0). Check whether you can complete it. If so print the Sudoku or else, print “Np”.

Consider the given sudoku,

Sudoku before solving

After solving,

Sudoku after solving

Backtracking Algorithm to solve Sudoku

  • Find row, col of a cell assigned with value = 0.
  • If there is no such row and column, return true
  • Repeat for digits from 0 to 9
  • a) If there is no conflict for digit at row, column, assign digit to row, column and recursively try to fill in rest of grid.
  • b) If recursion is successful, return true.
  • c) Else, remove the digit and try another digit.
  • If all digits have been tried and nothing worked, return false.

Program to solve Sudoku using backtracking is given below.

/* C++ program to solve Sudoku using backtracking */

#include<iostream>
using namespace std;
int sud[9][9];
bool isSafe(int row,int col,int num)
{
   for(int i=0;i<9;i++)
   {
       if(sud[row][i] == num)
           return false;
       if(sud[i][col] == num)
           return false;
   }
   int rowS=row-row%3,colS=col-col%3;
   for(int i=rowS;i<rowS+3;i++)
   {
       for(int j=colS;j<colS+3;j++)
       {
           if(sud[i][j] == num)
               return false;
       }
   }
   return true;
}
bool solveSudoko()
{
   int row,col;
   bool flag=false;
   for(row=0;row<9;row++)
   {
       for(col=0;col<9;col++)
       {
           if(sud[row][col] == 0)
              {
                  flag=true;
                  break;
              }
       }
       if(flag)
           break;
   }
   if(!flag)
       return true;
   for(int num = 1;num<10;num++)
   {
       if(isSafe(row,col,num))
       {
           sud[row][col]=num;
           if(solveSudoko())
               return true;
           sud[row][col]=0;
       }
   }
   return false;
}
int main()
{
   for(int i=0;i<9;i++)
       for(int j=0;j<9;j++)
           cin>>sud[i][j];
   if(solveSudoko())
   {
       for(int i=0;i<9;i++)
       {
           for(int j=0;j<9;j++)
               cout<<sud[i][j];
           cout<<endl;   
       }
   }
   else
   {
       cout<<“No”;
   }
}

Test Case 1

I/P
3 0 6 5 0 8 4 0 0
5 2 0 0 0 0 0 0 0
0 8 7 0 0 0 0 3 1
0 0 3 0 1 0 0 8 0
9 0 0 8 6 3 0 0 5
0 5 0 0 9 0 6 0 0
1 3 0 0 0 0 2 5 0
0 0 0 0 0 0 0 7 4
0 0 5 2 0 6 3 0 0

O/P
3 1 6 5 7 8 4 9 2
5 2 9 1 3 4 7 6 8
4 8 7 6 2 9 5 3 1
2 6 3 4 1 5 9 8 7
9 7 4 8 6 3 1 2 5
8 5 1 7 9 2 6 4 3
1 3 8 9 4 7 2 5 6
6 9 2 3 5 1 8 7 4
7 4 5 2 8 6 3 1 9

Test Case 2

I/P
3 2 6 5 0 8 4 0 0
5 0 0 0 0 0 0 0 0
0 8 7 0 0 0 0 3 1
0 0 3 0 1 0 0 8 0
9 0 0 8 6 3 0 0 5
0 0 0 0 9 0 6 0 0
1 3 0 0 0 0 2 5 0
0 0 0 0 0 0 0 7 4
0 5 0 2 0 6 3 0 0

O/P
No

Test Case 3

I/P
0 0 0 0 0 0 2 0 0
0 8 0 0 0 7 0 9 0
6 0 2 0 0 0 5 0 0
0 7 0 0 6 0 0 0 0
0 0 0 9 0 1 0 0 0
0 0 0 2 0 0 4 0 0
0 0 5 0 0 0 6 0 3
0 9 0 4 0 0 0 7 0
0 0 6 0 0 0 0 0 0

O/P
9 1 7 3 4 5 2 6 8
5 8 4 6 2 7 3 9 1
6 3 2 1 8 9 5 4 7
2 7 1 5 6 4 8 3 9
4 5 8 9 3 1 7 2 6
3 6 9 2 7 8 4 1 5
1 4 5 7 9 2 6 8 3
8 9 3 4 5 6 1 7 2
7 2 6 8 1 3 9 5 4

Test Case 4

I/P

0 0 0 1 0 5 0 6 8
0 0 0 0 0 0 7 0 1
9 0 1 0 0 0 0 3 0
0 0 7 0 2 6 0 0 0
5 0 0 0 0 0 0 0 3
0 0 0 8 7 0 4 0 0
0 3 0 0 0 0 8 0 5
1 0 5 0 0 0 0 0 0
7 9 0 4 0 1 0 0 0

O/P
4 7 3 1 9 5 2 6 8
8 5 6 3 4 2 7 9 1
9 2 1 6 8 7 5 3 4
3 4 7 5 2 6 1 8 9
5 8 2 9 1 4 6 7 3
6 1 9 8 7 3 4 5 2
2 3 4 7 6 9 8 1 5
1 6 5 2 3 8 9 4 7
7 9 8 4 5 1 3 2 6

Test Case 5

I/P
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0

O/P
1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 8 9 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 9 7 2 1 4 3 6 5
5 3 1 6 4 2 9 7 8
6 4 2 9 7 8 5 3 1
9 7 8 5 3 1 6 4 2