Backtracking Target: 15s
Find empty cell, try digits 1-9 with constraint checks (row, col, 3x3 box). Backtrack on failure.
def solveSudoku(board):
def is_valid(r, c, ch):
br, bc = 3*(r//3), 3*(c//3)
for i in range(9):
if board[r][i] == ch: return False
if board[i][c] == ch: return False
if board[br + i//3][bc + i%3] == ch: return False
return True
def solve():
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for ch in '123456789':
if is_valid(i, j, ch):
board[i][j] = ch
if solve(): return True
board[i][j] = '.'
return False
return True
solve()Type it from memory. Go.