I have written the following code to solve a Sudoku game with the backtracking method. It is possible to print the correct result, but I haven't found a way to get the same result as return value instead of printing it. How do I have to change the program to make it work?
import numpy as np
def find_possible(sudoku,r,c):
"""returns the possible Values as numpy array for a given position"""
position = sudoku[r, c]
if position == 0:
line = sudoku[r, :]
column = sudoku[: ,c]
r0 = (r//3)*3
c0 = (c//3)*3
square = sudoku[r0:r0+3,c0:c0+3]
numbers = np.arange(1, 10)
blocked_numbers = np.unique(np.append(np.append(line,column),square))
return np.setdiff1d(numbers,blocked_numbers)
else: return np.array([])
def backtrack(sudoku):
"""solve the game with the backtracking method"""
for r in range(9):
for c in range(9):
list_of_possible = find_possible(sudoku,r, c)
if sudoku[r,c] == 0:
for i in range(len(list_of_possible)):
sudoku[r,c] = list_of_possible[i]
backtrack(sudoku)
sudoku[r,c] = 0
return
result = sudoku
print(result)
table = np.array([[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]])
backtrack(table)
EDIT
If the print is replaced by a return, the return value is still None because of the first return. And if I give the first return the value of the sudoku Matrix, the output is not the final result
You're not passing the result "back along the track" to the original call of your backtrack function. (Result meaning that the sudoku has been solved.) Your print works, because you get to that line exactly one time: when your for loops finished after there are no zeros left. However, the solving doesn't stop there and your "tree" of backtrack calls continues. You can verify this by looking at table: at some point it had been fully solved (no zeros left), but if you print it at the end, there will be zeros in there again.
With the following changes, your function either returns None (like you had before, I just added the None for explicitness) or the solved sudoku in sudoku. Inside the for loop, result stores the result of the call to backtrack and we can test if the result was None (and we have to keep on solving) or we're done and can return result (either to the previous backtrack call, or to the original call outside the function).
def backtrack(sudoku):
"""solve the game with the backtracking method"""
for r in range(9):
for c in range(9):
list_of_possible = find_possible(sudoku, r, c)
if sudoku[r, c] == 0:
for i in range(len(list_of_possible)):
sudoku[r, c] = list_of_possible[i]
result = backtrack(sudoku)
if result is not None:
return result
sudoku[r, c] = 0
return None
return sudoku
By the way, the result name is just another reference to the same object as sudoku. I thought it might help understand what's happening, but you don't really need it:
def backtrack(sudoku):
"""solve the game with the backtracking method"""
for r in range(9):
for c in range(9):
list_of_possible = find_possible(sudoku, r, c)
if sudoku[r, c] == 0:
for i in range(len(list_of_possible)):
sudoku[r, c] = list_of_possible[i]
if backtrack(sudoku) is not None:
return sudoku
sudoku[r, c] = 0
return None
return sudoku
Also, try to start using a linter like Pylint or flake8 which will analyze your code a little bit for some improvements. For example, in Python, instead of
for i in range(len(list_of_possible)):
you can just write
for possible in list_of_possible: