# Sudoku

by Chris Luedtke in AlgoSIG 4

## Challenge

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:

```board = [
['5', '3', '.', '.', '7', '.', '.', '.', '.'],
['6', '.', '.', '1', '9', '5', '.', '.', '.'],
['.', '9', '8', '.', '.', '.', '.', '6', '.'],
['8', '.', '.', '.', '6', '.', '.', '.', '3'],
['4', '.', '.', '8', '.', '3', '.', '.', '1'],
['7', '.', '.', '.', '2', '.', '.', '.', '6'],
['.', '6', '.', '.', '.', '.', '2', '8', '.'],
['.', '.', '.', '4', '1', '9', '.', '.', '5'],
['.', '.', '.', '.', '8', '.', '.', '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([str(i) for i in range(1, 10)])

# create a dict of slot locations to fill
d = {}
i = 0
for r_i in range(9):
for c_i in range(9):
if board[r_i][c_i] == '.':
d[i] = (r_i, c_i)
i += 1

# 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:
# look up the current row/column slot location from the dict
r_i = d[i][0]
c_i = d[i][1]

# get set of numbers already used in row/col/box constraints
row_vals = set(board[r_i])
col_vals = set(board[i][c_i] for i in range(9))
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 all values
candidates = val_set - row_vals - col_vals - box_vals
# filter candidates to those greater than current placement
cur_val = board[r_i][c_i]
candidates = sorted(c for c in candidates if c > cur_val)

# backtrack if no valid candidates exist
if not candidates:
board[r_i][c_i] = '.'
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
```