Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
DFS + minimum variants solution in Clear category for Sudoku Solver by ogoro
from collections import deque
def print_grid(grid):
"printout grid"
print('=' * 20)
print(' ' * ((len(grid) - 1) // 10 + 2) + ''.join(str(i % 10) for i in range(len(grid[0]))))
for y, row in enumerate(grid):
print(f'{y:{(len(grid) - 1) // 10 + 1}d}', end=' ')
for x, cell in enumerate(row):
print(grid[y][x], end='')
print('\r')
def checkio(grid):
def get_unused(grid):
# get sets of un-used digits for each row, column and quadrant
ROW, COL, QUA = dict(), dict(), dict()
for j in range(9):
COL[j] = set(range(1, 10))
QUA[j] = set(range(1, 10))
for i, row in enumerate(grid):
ROW[i] = set(range(1, 10)) - set(row)
for j, cell in enumerate(row):
COL[j] -= {cell}
qua_index = 3*(i//3) + j//3
QUA[qua_index] -={cell}
return ROW, COL, QUA
def get_minimum_variants(grid):
# get cell and variant of digits - with minimum length of possible digits
ROW, COL, QUA = get_unused(grid)
min_variants = set()
min_variants_len = 9
min_variants_cell = ()
for i in ROW:
# print('Checking ROW:', i)
for j in COL:
# print(' Checking CELL:', (i, j), grid[i][j])
qua_index = 3*(i//3) + j//3
variants = ROW[i] & COL[j] & QUA[qua_index]
# print(' Variants:', variants)
if len(variants) < min_variants_len and grid[i][j] == 0:
min_variants = variants
min_variants_len = len(variants)
min_variants_cell = (i, j)
return min_variants, min_variants_cell
# main loop
results = []
q = deque([(grid, 0)])
while q:
current_grid, level = q.pop()
min_variants, min_variants_cell = get_minimum_variants(current_grid)
zero_count = sum(sum(1 for e in row if e == 0) for row in current_grid)
# print('### Level:', level)
# print(' Minimum variants:', min_variants, min_variants_cell)
# print(' Zero count:', zero_count)
# if all cells filled in - return result
if zero_count == 0:
print('Puzzle complete')
print_grid(current_grid)
return current_grid
# if cell can not be filled in due to conflicting digits - drop branch
if min_variants == set():
# print('!!! Empty variants for:', min_variants_cell)
# print_map(current_grid)
continue
for variant in min_variants:
new_grid = [[e for e in row] for row in current_grid]
i, j = min_variants_cell
new_grid[i][j] = variant
# print(' Adding:', variant, 'to level:', level+1)
# print_map(new_grid)
# print()
q.append((new_grid, level+1))
# maximum level limit
if level > 60:
print('!!! Level 60 reached')
print_map(current_grid)
raise StopIteration
if __name__ == '__main__':
#These "asserts" using only for self-checking and not necessary for auto-testing
assert checkio([[0, 7, 1, 6, 8, 4, 0, 0, 0],
[0, 4, 9, 7, 0, 0, 0, 0, 0],
[5, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 0, 0, 0, 0, 5, 0, 4],
[0, 0, 0, 3, 0, 7, 0, 0, 0],
[2, 0, 3, 0, 0, 0, 0, 9, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 9],
[0, 0, 0, 0, 0, 3, 7, 2, 0],
[0, 0, 0, 4, 9, 8, 6, 1, 0]]) == [[3, 7, 1, 6, 8, 4, 9, 5, 2],
[8, 4, 9, 7, 2, 5, 3, 6, 1],
[5, 6, 2, 9, 3, 1, 4, 7, 8],
[6, 8, 7, 2, 1, 9, 5, 3, 4],
[9, 1, 4, 3, 5, 7, 2, 8, 6],
[2, 5, 3, 8, 4, 6, 1, 9, 7],
[1, 3, 6, 5, 7, 2, 8, 4, 9],
[4, 9, 8, 1, 6, 3, 7, 2, 5],
[7, 2, 5, 4, 9, 8, 6, 1, 3]], "first"
assert checkio([[5, 0, 0, 7, 1, 9, 0, 0, 4],
[0, 0, 1, 0, 3, 0, 5, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 8, 5, 9, 7, 2, 6, 4, 0],
[0, 0, 0, 6, 0, 1, 0, 0, 0],
[0, 2, 6, 3, 8, 5, 9, 1, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 0, 5, 0, 2, 0, 0],
[8, 0, 0, 4, 9, 7, 0, 0, 6]]) == [[5, 6, 8, 7, 1, 9, 3, 2, 4],
[9, 7, 1, 2, 3, 4, 5, 6, 8],
[2, 3, 4, 5, 6, 8, 7, 9, 1],
[1, 8, 5, 9, 7, 2, 6, 4, 3],
[3, 9, 7, 6, 4, 1, 8, 5, 2],
[4, 2, 6, 3, 8, 5, 9, 1, 7],
[6, 1, 9, 8, 2, 3, 4, 7, 5],
[7, 4, 3, 1, 5, 6, 2, 8, 9],
[8, 5, 2, 4, 9, 7, 1, 3, 6]], "second"
print('Local tests done')
Nov. 20, 2020
