LC 0037 [H] Sudoku Solver - ALawliet/algorithms GitHub Wiki
https://leetcode.com/problems/sudoku-solver/discuss/15959/Accepted-Python-solution
subgrid offset calculation
v
[0 1 2][3 4 5][6 7 8]
[1 ][ ][ ]
[2 ][ ][ ]
loop 1 -> 9:
so 1st num of subgrid 2 is [3*0+0][3*1+0] = [0][3]
so 2nd num of subgrid 2 is [3*0+1][3*1+1] = [0][4]
so 3rd num of subgrid 2 is [3*0+2][3*1+2] = [0][5]
so 4th num of subgrid 2 is [3*0+1][3*1+0] = [1][3]
so 1st num of subgrid 2 is [3*0 + 0][3*1 + 0] = [0][3] top left diag
so 2nd num of subgrid 2 is [3*0 + 1][3*1 + 1] = [1][4] middle diag
so 3rd num of subgrid 2 is [3*0 + 2][3*1 + 2] = [2][5] bottom right diag
so 4th num of subgrid 2 is [3*0 + 1][3*1 + 0] = [1][3] down
for i in range(9):
if board[i][c] == num: return False # already in row, row is invalid
if board[r][i] == num: return False # already in col, col is invalid
div, mod = divmod(i, 3)
if board[3*(r//3) + div][3*(c//3) + mod] == num: return False # already in box, box is invalid
return True
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
def valid(r, c, num): # row is valid, col is valid, box is valid
for i in range(9):
if board[i][c] == num: return False # already in row, row is invalid
if board[r][i] == num: return False # already in col, col is invalid
div, mod = divmod(i, 3)
if board[3*(r//3) + div][3*(c//3) + mod] == num: return False
return True
def helper(board):
for r in range(9):
for c in range(9):
if board[r][c] == '.':
for num in range(1, 9+1): # try numbers 1-9
num = str(num)
if valid(r, c, num):
board[r][c] = num # choose
if helper(board): return True # recurse
board[r][c] = '.' # unchoose
return False
return True
return helper(board)