This is a working code that solves the sudoku:
def is_valid(board, row, col, num):
for i in range(9):
if board[row][i] == num:
return False
for i in range(9):
if board[i][col] == num:
return False
box_row = (row - row % 3)
box_col = (col - col % 3)
for i in range(3):
for j in range(3):
if board[box_row + i][box_col + j] == 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, row, col, num):
board[row][col] = num
solve(board)
board[row][col] = 0
return False
print(np.matrix(board))
solve(board)
The part that confuses me is:
if board[row][col] == 0:
for num in range(1,10):
if is_valid(board, row, col, num):
board[row][col] = num
solve(board)
board[row][col] = 0
return False
how is this part working? I know it will assign the number, to the current row and col THEN, run the solve() function again, so, when will the program run this:
board[row][col] = 0
because as I understand it, the code won't run unless there's a 0 already. Then the program will check if the number is valid or not. also if there's no num [1~9] that is valid, won't it return false and quit the function?
talking about it makes my head spin, I know it's even hard to explain, I googled it.
Edit:
this is the board I'm dealing with:
board_1 = [
[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]
]
Output:
[[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]]
There are two cases where the solve function returns. I'll rewrite the code to make it sweeter (but yours works too)*:
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, row, col, num):
board[row][col] = num
solve(board)
board[row][col] = 0
return False
return True
So, whenever the solve method reaches one of those return statements, it returns to the method that called it. Note that there are a two if-statements outside the call to solve. These can evaluate to False. And if they evaluate to False often enough, one of the return statements will be reached. That's how you get to board[row][col] = 0
If you want to see the solved Sudoku, you have to repeat print(np.matrix(board)) after the call to solve at the very end too.
*Side notes:
None or False which is bad style because bool(None) evaluates to False too. Why does it return None? That's because no return statement at the end of a function is equivalent to return None.return unless you need the True/False later. That's because solve(board) is not assigned to anything.