Explore
Placement Prep

Edit

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,

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