# 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,

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