I'm struggling to make this work. It gets a few digits right, but I don't know where the problem is. I've read various other codes and while I understand how they work, I don't know where the problem with my code is. I've tried multiple things and this is the closest I've come.
board = [
[0, 9, 0, 0, 0, 0, 0, 1, 0],
[8, 0, 4, 0, 2, 0, 3, 0, 7],
[0, 6, 0, 9, 0, 7, 0, 2, 0],
[0, 0, 5, 0, 3, 0, 1, 0, 0],
[0, 7, 0, 5, 0, 1, 0, 3, 0],
[0, 0, 3, 0, 9, 0, 8, 0, 0],
[0, 2, 0, 8, 0, 5, 0, 6, 0],
[1, 0, 7, 0, 6, 0, 4, 0, 9],
[0, 3, 0, 0, 0, 0, 0, 8, 0],
]
def p(board):
for i in board:
print(i)
def find(board):
for row in range(9):
for col in range(9):
if board[row][col] == 0:
return row, col
return 1
def check_horizontal(board, row, number):
for i in range(0, 9):
if board[row][i] == number:
return False
return True
def check_vertical(board, col, number):
for i in range(0, 9):
if board[i][col] == number:
return False
return True
def check_sqaure(board, row, col, number):
a = int(row / 3)
b = int(col / 3)
for i in range(a * 3, a * 3 + 3):
for j in range(b * 3, b * 3 + 3):
if board[i][j] == number:
return False
return True
def check_all(board, row, col, number):
if check_horizontal(board, row, number) and check_vertical(board, col, number) and check_sqaure(board, row, col,number):
return True
def play(board):
if find(board) == 1:
return 1
row, col = find(board)
for i in range(1, 10):
if check_all(board, row, col, i):
board[row][col] = i
if play(board) == 1:
return board
else:
if check_all(board, row, col,board[row][col] + 1):
board[row][col] = board[row][col] + 1
play(board)
p(board)
and this is the output:
[7, 9, 2, 3, 4, 8, 6, 1, 5]
[8, 5, 4, 6, 2, 0, 3, 0, 7]
[0, 6, 0, 9, 0, 7, 0, 2, 0]
[0, 0, 5, 0, 3, 0, 1, 0, 0]
[0, 7, 0, 5, 0, 1, 0, 3, 0]
[0, 0, 3, 0, 9, 0, 8, 0, 0]
[0, 2, 0, 8, 0, 5, 0, 6, 0]
[1, 0, 7, 0, 6, 0, 4, 0, 9]
[0, 3, 0, 0, 0, 0, 0, 8, 0]
The correct result would be:
[7, 9, 2, 3, 5, 4, 6, 1, 8]
[8, 5, 4, 1, 2, 6, 3, 9, 7]
[3, 6, 1, 9, 8, 7, 5, 2, 4]
[9, 4, 5, 6, 3, 8, 1, 7, 2]
[2, 7, 8, 5, 4, 1, 9, 3, 6]
[6, 1, 3, 7, 9, 2, 8, 4, 5]
[4, 2, 9, 8, 1, 5, 7, 6, 3]
[1, 8, 7, 2, 6, 3, 4, 5, 9]
[5, 3, 6, 4, 7, 9, 2, 8, 1]
I see a couple issues with your play function.
The first issue is that you're not backtracking properly. Backtracking means you need to mark the space on the board you've been testing as unknown when you give up on the current partial solution. You currently have some strange code that tries to jump ahead if the recursion didn't find a solution. I think you should remove these lines:
else:
if check_all(board, row, col,board[row][col] + 1):
board[row][col] = board[row][col] + 1
Instead, you need to reset if the loop fails to find any solution. So put this at the end of the code, outside the loop:
board[row][col] = 0
The other issue is that you've got some mixed up logic about what the return value should be from play. In the base case, you're returning the sentinel value 1, and your later recursive code checks for this. But the later code will return board instead of the sentinel value if it thinks it got a solution from the recursion. You need to pick one of those and be consistent with it! The other side of this is that you're relying upon the default return value of None to indicate a failure when you fall off the end of the function. You should probably be explicit about that return value, by adding return None.
Here's how I'd do it, returning the board:
def play(board):
if find(board) == 1:
return board # first change, return the board here!
row, col = find(board)
for i in range(1, 10):
if check_all(board, row, col, i):
board[row][col] = i
if play(board) is not None: # second change, check for a non-None value, not == 1
return board
board[row][col] = 0 # third change, do proper backtracking (replaced three lines)
return None # fourth change, be explicit about our return value on failure
There's still a small wart where you call find twice, but it doesn't make the code wrong, just a bit slower than necessary. You could improve it by changing the first few lines:
coords = find(board)
if coords == 1:
return board
row, col = coords
I'd also prefer to use None as the sentinel for a failed find, but that's more an issue of taste than anything genuinely wrong or inefficient.