LC 0037 [H] Sudoku Solver - ALawliet/algorithms GitHub Wiki

https://leetcode.com/problems/sudoku-solver/discuss/15959/Accepted-Python-solution

• https://www.youtube.com/watch?v=JzONv5kaPJM
• https://www.youtube.com/watch?v=wWUDo2FkdMc

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)