ChiPy Algorithms SIGDescription
Write a program to solve any Sudoku puzzle by filling the empty cells. In a sudoku solution, each digit 1-9 must occur exactly once in each row, each column, and in each of the 9 3x3 sub-boxes of the grid.
Sample input (0 represents a “blank” slot):
board = [
[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]
]
Solution
# check out https://en.wikipedia.org/wiki/Sudoku_solving_algorithms
from typing import List
def solve_sudoku(board: List[List[str]]) -> List[List[str]]:
# create a set of all values that may be placed
val_set = set(range(1, 10))
# create a list of slot locations to fill
d = []
for r_i in range(9):
for c_i in range(9):
if board[r_i][c_i] == 0:
d.append((r_i, c_i))
# Iterate over slots, inserting numbers that are valid.
# If no valid number possible, backtrack to previous slot
# and increment by 1
i = 0
while True:
r_i, c_i = d[i] # row and column index location of the current empty slot
# set of numbers already used in row
row_vals = set(board[r_i])
# set of numbers already used in col
col_vals = set(board[i][c_i] for i in range(9))
# set of numbers already used in sub-grid
b_r_i = r_i // 3 * 3
b_c_i = c_i // 3 * 3
box_vals = set(
board[b_r_i ][b_c_i:b_c_i + 3] +
board[b_r_i + 1][b_c_i:b_c_i + 3] +
board[b_r_i + 2][b_c_i:b_c_i + 3]
)
# subtract already-used numbers from the set of possible values
candidates = val_set - row_vals - col_vals - box_vals
# filter candidates to those greater than current placement
current_value = board[r_i][c_i]
candidates = sorted(c for c in candidates if c > current_value)
# backtrack if no valid candidates exist
if not candidates:
board[r_i][c_i] = 0
i -= 1
continue
# otherwise place the next greater candidate in the slot
else:
board[r_i][c_i] = candidates[0]
# board is solved if last empty slot is filled
if i == len(d) - 1:
return board
i += 1