I have built a sudoku solver backtracking algorithm in python just to find out it does not work. I looked at examples on the internet and saw that there is only one thing which they are doing differently, compared to mine. I changed my code accordingly and my program is now working fine.
Here is the working code:
sudoku = []
next_empty_pos = [0,0]
# Check if the number is already used in the given row
def valid_in_row(number,row):
for i in range(9):
if(sudoku[row][i] == number):
return False
return True
# Check if the number is already used in the given column
def valid_in_col(number,col):
for i in range(9):
if(sudoku[i][col] == number):
return False;
return True;
# Check if the number is already used in the given 3x3 box
def valid_in_box(number,row,col):
# Find where 3x3 row and col starts
col_start = col-col%3
row_start = row-row%3
# Loop through the 3 columns and 3 rows
for i in range(3):
for z in range(3):
if(sudoku[i+row_start][z+col_start] == number):
return False
return True
# Check if the position is valid for the given number by checking all three conditions above
def position_valid(number,row,col):
return valid_in_row(number,row) and valid_in_col(number,col) and valid_in_box(number,row,col)
# Find if there are any empty cells left and assign the next empty cell
def empty_position_exists():
for row in range(9):
for col in range(9):
if(sudoku[row][col] == 0):
global next_empty_pos
next_empty_pos = [row,col]
return True
return False
# Solve the sudoku
def solve_sudoku():
# If there are no more empty cells, we are finished
if(not empty_position_exists()):
return True
row=next_empty_pos[0]
col=next_empty_pos[1]
# Try numbers from 1
for posssible_number in range(1,10):
if(position_valid(posssible_number,row,col)):
sudoku[row][col] = posssible_number
# If the next function call evalutes to true, then this should be true as well
if(solve_sudoku()):
return True
# If the above did not work then, set the number back to 0 (unassgined)
sudoku[row][col] = 0
# Return false if none of the numbers were good
return False
The difference to my original code was that I was passing next_empty_pos[0] and next_empty_pos[1] directly in my solve_sudoku function and not declaring them as seperate row and col variables outside of the for loop.
My function looked like this:
# Solve the sudoku
def solve_sudoku():
# If there are no more empty cells, we are finished
if(not empty_position_exists()):
return True
# Try numbers from 1
for posssible_number in range(1,10):
if(position_valid(posssible_number,next_empty_pos[0],next_empty_pos[1])):
sudoku[next_empty_pos[0]][next_empty_pos[1]] = posssible_number
# If the next function call evalutes to true, then this should be true as well
if(solve_sudoku()):
return True
# If the above did not work then, set the number back to 0 (unassgined)
sudoku[next_empty_pos[0]][next_empty_pos[1]] = 0
# Return false if none of the numbers were good
return False
Could someone explain why my version was not working?
Thanks in advance.
empty_position_exists changes next_empty_pos. When solve_sudoku calls itself recursively, empty_position_exists is called from the recursive invocation, changing next_empty_pos. The result is that when you access those values after the recursive call returns, they have changed. That's why the two versions behave differently.