I am learning backtracking and recursion. I wrote a code for solving a Sudoku problem but I am getting a wrong output and I can't figure out why ? Please help me out!
def print_sudoku(arr):
for i in range(9):
for j in range(9):
print(arr[i][j], end = '')
print('\n')
def empty_space(arr, l):
for i in range(9):
for j in range(9):
if(arr[i][j] == 0):
l[0] = i
l[1] = j
return True
else:
return False
def check_row(arr, row, num):
for j in range(9):
if arr[row][j] == num:
return False
return True
def check_col(arr, col, num):
for i in range(9):
if arr[i][col] == num:
return False
return True
def check_grid(arr, row, col, num):
for i in range(3):
for j in range(3):
if arr[row + i][col + j] == num:
return False
return True
def solve_sudoku(arr):
l = [0, 0]
if not empty_space(arr, l):
return True
else:
row = l[0]
col = l[1]
for k in range(1, 10):
num = k
if check_row(arr, row, num) and check_row(arr, row, num) and check_grid(arr, row - (row%3), col - (col%3), num):
arr[row][col] = k
if solve_sudoku(arr):
return True
arr[row][col] = 0
return False
if __name__ == "__main__":
grid = [[0 for x in range(9)] for y in range(9)]
grid = [[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]]
if solve_sudoku(grid):
print(' Sudoku Solved ')
print_sudoku(grid)
else:
print("Sudoku can't be solved")
The output I am getting is this:
Sudoku Solved
316578429
524139678
987246531
263415789
917863245
458297613
134789256
268135974
795246318
While the correct output is:
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
Just a guess:
if check_row(arr, row, num) and check_row(arr, row, num) and check_grid(arr, row - (row%3), col - (col%3), num):
You should probably call check_col here.