Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Check only possible solutions solution in Speedy category for Sudoku Solver by damiankulus
def checkio(grid):
digits = {i + 1 for i in range(9)}
blocks = [[grid[i][j] for i in range(b // 3 * 3, b // 3 * 3 + 3) for j in range(b % 3 * 3, b % 3 * 3 + 3)]
for b in range(9)]
block_positions = {(i, j): j // 3 + i // 3 * 3 for i in range(9) for j in range(9)}
uses_branches = list()
while True:
branch = list()
moves = list()
# possible numbers in each row
steps_rows = {i: digits - set(grid[i]) for i in range(9)}
# possible numbers in each column
steps_cols = {j: digits - set(grid[i][j] for i in range(9)) for j in range(9)}
# possible numbers in each block
steps_blocks = {b: digits - set(blocks[b]) for b in range(9)}
# empty places in sudoku
empty_places = [(i, j) for i in range(9) for j in range(9) if not grid[i][j]]
while True:
if not empty_places:
break
# possible numbers in each cell
steps_cells = [(i, j, tuple(steps_rows[i] & steps_cols[j] & steps_blocks[b]))
for (i, j), b in block_positions.items() if (i, j) in empty_places]
# cell with min number of possible solutions
i, j, solutions = min(steps_cells, key=lambda c: len(c[2]))
if not solutions:
# without solutions - stop, wrong way
uses_branches.append(branch)
break
if len(solutions) > 1:
# many solutions - create branches
n_sol = [s for s in solutions if branch + [(i, j, s), ] not in uses_branches]
if not n_sol:
uses_branches.append(branch)
break
next_solution = n_sol[0]
branch.append((i, j, next_solution))
else:
# one solution
next_solution = solutions[0]
# update state
moves.append((i, j, next_solution))
empty_places.remove((i, j))
b = block_positions[i, j]
steps_rows[i].remove(next_solution)
steps_cols[j].remove(next_solution)
steps_blocks[b].remove(next_solution)
if not empty_places:
break
for m in moves:
grid[m[0]][m[1]] = m[2]
return grid
Feb. 13, 2022
Comments: