Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Solving Sudoku Using Backtracking | FACE Prep

Published on 11 Mar 2020

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.


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



Code:

C++
Python 3

Output
Input -
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
Output -
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



Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises