This is my recursive sudoku solver. Pretty self-explanatory:
def is_valid(board, num, row, col):
# check row
for i in range(9):
if board[i][col] == num:
return False
# check column
for i in range(9):
if board[row][i] == num:
return False
# check square
square_w = (row // 3) * 3
square_h = (col // 3) * 3
for sRow in range(square_w, square_w + 3):
for sCol in range(square_h, square_h + 3):
if board[sRow][sCol] == num:
return False
return True
def solve(board):
for row in range(9):
for col in range(9):
if board[row][col] == 0:
for num in range(1, 10):
if is_valid(board, num, row, col):
board[row][col] = num
yield board
yield from solve(board)
board[row][col] = 0
yield board
return
yield board
And this is the board I am running the solver on:
bo = [
[7,8,0,4,0,0,1,2,0],
[6,0,0,0,7,5,0,0,9],
[0,0,0,6,0,1,0,7,8],
[0,0,7,0,4,0,2,6,0],
[0,0,1,0,5,0,9,3,0],
[9,0,4,0,6,0,0,0,5],
[0,7,0,3,0,0,0,1,2],
[1,2,0,0,0,7,4,0,0],
[0,4,9,2,0,6,0,0,7]
]
The problem is that when I call solve and iterate the yielded boards, the boards continue to generate even after getting the result (at the bottom most yield board in the solve function).
How can I make sure that the last value in the generator is the solved board?
There are some indentation problems in your code. At the time of writing both the return and yield from statements should be indented one level more.
To stop the generation of more boards once you have it solved, you should check that the board is solved. The code does not do this anywhere.
As you correctly indicate, the board is solved when you reach the last statement in the solve function, and the function returns there. You could use this moment to mark the board so to make it easier for the caller to also know that the board was solved. As you already mutate the same board throughout the algorithm (instead of yielding copies), I suppose you could just mutate the board once more in order to indicate it was solved. For instance, you could store a 0 in the top-left corner. This can be checked by the caller, who can then immediately return:
def solve(board):
for row in range(9):
for col in range(9):
if board[row][col] == 0:
for num in range(1, 10):
if is_valid(board, num, row, col):
board[row][col] = num
yield board
yield from solve( board) # corrected wrong indentation
if board[0][0] == 0: # was the board already solved?
return # then get out of here!
board[row][col] = 0 # better placed at this indentation
yield board # better placed at this indentation
return # corrected wrong indentation
# the board is the solution: no need to yield it as it was already yielded
board[0][0] = 0 # mark that no more boards should be yielded