I am trying to create a sudoku solver that uses recursive backtracking, however, I am not using any for loops in my program. This makes it difficult since when using the backtracking method, I need to use a for loop to iterate through the guesses from 1 to 9. Can anyone tell me how I can fix my recursive helper function that generates valid guesses?
def solve_sudoku(puzzle):
# solve sudoku using backtracking technique
# our puzzle is a list of lists, with each inner list being a row
# return whether a solution exists
# if solution exists, solution is printed in main portion of code
# step 1: choose somewhere to make a guess (iterates through puzzle looking for 0, which is a blank)
row, column = find_next_empty(puzzle)
# step 1.1: if there are no remaining empty spots, we must be done
if row is None:
return True
# generate a guess
trial = guess(puzzle, row, column)
# if there was no valid guess available, and guess() returned 0
if trial == 0:
return False
print(str(trial) + ' was placed.')
# update the board by placing the valid guess
puzzle[row][column] = trial
# recursively call the solver
if solve_sudoku(puzzle):
return True
# backtracking portion (this is the portion that I do not think is functioning properly)
puzzle[row][column] = 0
# return False if no solutions to the puzzle
return False
# create function to recursively guess from 1 - 9, return the valid guess value
def guess(puzzle, row, column, n = 1):
# stopping condition
if n > 9:
return 0
# is_valid() function is working properly, basically returns True if the same number does not exist in same row, column or 3x3 matrix
if is_valid(puzzle, n, row, column):
return n
return guess(puzzle, row, column, n + 1)
Output Images: Input Board where 0s represent blanks
My Board's output which returns False after failing to find a solution for the last blank on row 1
while?