This is leetcode #37 (Sudoku solver).
I have a question regarding modifying an input list in-place within a recursive function. The code below pretty much does the job as the print(board) does print the correct solution (I'm sure the efficiency can be improved but that is not the point of this question lol). However, I have trouble saving the modified board (or its copy) - printing board at the end always gives the original input.
I know I can create another path variable within the back-tracking function to record all the filled numbers, but it seems a bit too clumsy... Is there an efficient way to save the modified input list when the solution is completed? Many thanks!
class Solution:
def solveSudoku(self, board):
def options(board, i, j):
numbers = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
choices = numbers.copy()
for col in range(9):
if board[i][col] in choices:
choices.remove(board[i][col])
for row in range(9):
if board[row][j] in choices:
choices.remove(board[row][j])
corner_x, corner_y = (i // 3) * 3, (j // 3) * 3
for row in range(corner_x, corner_x + 3):
for col in range(corner_y, corner_y + 3):
if board[row][col] in choices:
choices.remove(board[row][col])
return choices
def back_tracking(board, pos):
if pos <= 81:
if pos == 81:
print(board)
return
else:
i, j = divmod(pos, 9)
if board[i][j] != '.':
back_tracking(board, pos + 1)
elif options(board, i, j) != []:
for choice in options(board, i, j):
board[i][j] = choice
back_tracking(board, pos + 1)
board[i][j] = '.'
back_tracking(board, 0)
return board
The problem is here:
for choice in options(board, i, j):
board[i][j] = choice
back_tracking(board, pos + 1) # <<< here
board[i][j] = '.'
In your implementation, even if the back_tracking call in the marked line actually solves the puzzle, the code proceeds to the next line. reverting the number to '.', and continuing with the next choice, ignoring the fact that the solution was already found. Eventually, it tries everything and reverts everything back, so the board is equal to the original.
In other words: Your code is already changing the values in place, but it is changing it all back to original after trying everything.
What I suggest you to do is: break the recursion and stop as soon as you get a valid solution. One option for this is to have an actual return value from your recursive back_tracking function, and return the board itself if the solution is found, otherwise, return None, so the algorithm continues iterating.
def back_tracking(board, pos):
if pos == 81:
return board
i, j = divmod(pos, 9)
if board[i][j] != '.':
return back_tracking(board, pos + 1)
if options(board, i, j) != []:
for choice in options(board, i, j):
board[i][j] = choice
if back_tracking(board, pos + 1):
return board
board[i][j] = '.'