I'm trying to make a sudoku solver using recursion by storing possible values in a dictionary with index as key and the set of possible values as value. Parameter b is just the board expressed as a single list, and .get_row, .get_col, .get_box methods return their respective values properly. If an entry in the dictionary has a set with a single element then it gets put into the board b, otherwise if there's no possible set with a single element a value gets picked from the set of possible numbers and the recursion starts. This is the full repeatable code:
class Sudoku:
def solve_it(self, board: List[List[str]]) -> None:
"""
:param board: sudoku board gets modified inplace at .create_board_from_list
:return: None
"""
unit_values = []
for i in range(len(board)): # flattening the board into unit_values
for j in range(len(board[i])):
unit_values.append(board[i][j])
self.go_through_recursive(board, unit_values)
def get_row(self, n: int, b): # retrieve all elements of nth row in the board
assert 0 <= n <= 8
return set(b[9 * n: 9 * (n + 1)])
def get_col(self, n: int, b): # retrieve all elements of nth col in the board
assert 0 <= n <= 8
return set(b[n::9])
def get_box(self, n: int, b): # retrieve all elements of nth box in the board
assert 0 <= n <= 8
return set(b[i] for i in range(81) if (i // 27) == (n // 3) and i % 9 // 3 == n % 3)
def go_through_recursive(self, board, b, d=False):
"""
:param board: sudoku board as matrix where each row is a line
:param b: sudoku board as a single long list
"""
numbers = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
while True:
if d:
return True
missing_dict = {} # populate missing_dict
for idx in range(len(b)):
if b[idx] == '.':
row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
# union of all the present values in current row, col and box
values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
values.remove('.')
missing_ones = numbers.difference(values) # possible values to input in the slot
if len(missing_ones) == 0: # impossible to continue
return False
missing_dict[idx] = missing_ones
old_count = b.count('.')
# now we iterate through the dictionary of possible values per index,
# if one index has a set with a single number it means that that's the only possible number so we store it
for idx, missings in missing_dict.items(): # store assured values
if len(missings) == 1:
b[idx] = missings.pop()
if b.count('.') == 0: # check if complete
self.create_board_from_list(board, b)
return True
if b.count('.') == old_count: # if no progress has been made
for idx, s in missing_dict.items(): # iterate through the dictionary
for number in s: # create a new board and store indecisive value then recur
if d:
return True
bb = b[:]
bb[idx] = number
d = self.go_through_recursive(board, bb)
def create_board_from_list(self, board, b):
temp_board = []
chunk = 9
for idx in range(0, len(b), chunk):
temp_board.append(b[idx: idx + chunk])
for idx in range(len(board)):
board[idx] = temp_board[idx]
print('done')
The issue I have is that once it completes, some numbers are repeated(either in the rows, cols or boxes).Also I 've noticed that if I check the possible values inside the ' store assured values ' loop it sometimes returns the whole range [1, 9] possibly being the reason of some rewriting:
row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
values.remove('.') # some of these values are [1, 9]
Given this board input:
board =
[[".",".","9","7","4","8",".",".","."],
["7",".",".",".",".",".",".",".","."],
[".","2",".","1",".","9",".",".","."],
[".",".","7",".",".",".","2","4","."],
[".","6","4",".","1",".","5","9","."],
[".","9","8",".",".",".","3",".","."],
[".",".",".","8",".","3",".","2","."],
[".",".",".",".",".",".",".",".","6"],
[".",".",".","2","7","5","9",".","."]]
the correct output is
board =
[["5","1","9","7","4","8","6","3","2"],
["7","8","3","6","5","2","4","1","9"],
["4","2","6","1","3","9","8","7","5"],
["3","5","7","9","8","6","2","4","1"],
["2","6","4","3","1","7","5","9","8"],
["1","9","8","5","2","4","3","6","7"],
["9","7","5","8","6","3","1","2","4"],
["8","3","2","4","9","1","7","5","6"],
["6","4","1","2","7","5","9","8","3"]]
while the code has the incorrect board
board =
[["3","1","9","7","4","8","6","5","2"],
["7","8","5","6","3","2","1","1","9"],
["4","2","6","1","5","9","8","7","3"],
["5","3","7","9","8","6","2","4","1"],
["2","6","4","3","1","7","5","9","8"],
["1","9","8","5","2","4","3","6","7"],
["9","7","1","8","6","3","4","2","5"],
["8","5","2","4","9","1","7","3","6"],
["6","4","3","2","7","5","9","8","4"]]
EDIT:
I changed the go_through_recursive to store the unique possible value directly into the board, in this case the only possible set length in the dictionary is 2 or greater. But this seems to get stuck in an infinite loop
def go_through_recursive(self, board, b, d=False):
"""
:param board: sudoku board as matrix where each row is a line
:param b: sudoku board as a single long list
"""
numbers = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
while True:
old_count = b.count('.')
missing_dict = {} # populate missing_dict
for idx in range(len(b)):
if b[idx] == '.':
row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
# union of all the present values in current row, col and box
values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
values.remove('.')
missing_ones = numbers.difference(values) # possible values to input in the slot
if len(missing_ones) == 0: # impossible to continue
return False
elif len(missing_ones) == 1:
b[idx] = missing_ones.pop()
else:
missing_dict[idx] = missing_ones
if b.count('.') == 0: # check if complete
self.create_board_from_list(board, b)
return True
if b.count('.') == old_count: # if no progress has been made
for idx, s in missing_dict.items(): # iterate through the dictionary
for number in s: # create a new board and store indecisive value then recur
bb = b[:]
bb[idx] = number
if self.go_through_recursive(board, bb):
return True
There are two issues in the first version of your code:
When you do b[idx] = missings.pop() you should exit the loop, because now missings is no longer up-to-date: by placing a number on the grid, this number is no longer allowed on some other empty cells, and this is not correctly reflected in the dictionary. This bug is the cause of getting the same number twice on the same line. The easy fix is to exit the loop right after this assignment, so that the dictionary can be rebuilt in the next iteration of the outer loop
Where you have the loop for number in s, you should consider that if none of these numbers leads to a solution (d is never True), you should not continue to try another entry from missing_dict, because if this one has no solution, it doesn't matter what you try elsewhere on the board: there is no solution. Instead you should backtrack with return False if this inner loop comes to an end without solution. This issue is the cause of an apparent "infinite" loop: there is an exponential number of combinations that gets tried in vain.
Not a problem, but as it is related to the second point's variable d: you have two places where you have if d:. You can easily avoid this duplication by placing this block right after you get the boolean back from recursion. Then you'll not even need the d parameter/variable.
Several other comments could be made, but correcting the above is enough to make it work. Here is the first version of your code with these corrections (The code comments indicate where a change was made):
def go_through_recursive(self, board, b): # No d argument needed
numbers = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
while True:
# Removed the `if d` block from here. See further down.
missing_dict = {}
for idx in range(len(b)):
if b[idx] == '.':
row, col, box = idx // 9, idx % 9, (idx // 27) * 3 + (idx % 9) // 3
values = self.get_row(row, b).union(self.get_col(col, b)).union(self.get_box(box, b))
values.remove('.')
missing_ones = numbers.difference(values)
if len(missing_ones) == 0:
return False
missing_dict[idx] = missing_ones
old_count = b.count('.')
for idx, missings in missing_dict.items():
if len(missings) == 1:
b[idx] = missings.pop()
# Must break here because now missing_dict
# is no longer up to date!
break
if b.count('.') == 0:
self.create_board_from_list(board, b)
return True
if b.count('.') == old_count:
# Only get one entry from this dictionary (no loop)
idx, s = next(iter(missing_dict.items()))
for number in s:
bb = b[:]
bb[idx] = number
# Not needed to assign to d,
# and the exit if-block can follow here
if self.go_through_recursive(board, bb):
return True
# This index has no possible value, so backtrack!
return False