Sudoku

36 Valid Sudoku

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

尋找 box index = (row / 3) * 3 + col / 3

def isValidSudoku(self, board: List[List[str]]) -> bool:
    row = [set() for _ in range(9)]
    col = [set() for _ in range(9)]
    box = [set() for _ in range(9)]
    
    for i in range(9):
        for j in range(9):
            if board[i][j] != '.':
                num = int(board[i][j])
                box_idx = (i//3) * 3 + j//3

                if num in row[i] or num in col[j] or num in box[box_idx]:
                    return False

                row[i].add(num)
                col[j].add(num)
                box[box_idx].add(num)
            
    return True

37 Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. Empty cells are indicated by the character '.'.

• for loop row and column

• loop 1 - 9, check if the number is valid on board[i][j], then recursive check new board

標定 box裡 1~9宮格的位置

• box_row = (row / 3) * 3 + i / 3

• box_col = (col / 3) * 3 + i % 3

def solveSudoku(self, board: List[List[str]]) -> None:
    """
    Do not return anything, modify board in-place instead.
    """
    self.solve(board)
    
    
def solve(self, board):
    for i in range(9):
        for j in range(9):
            if board[i][j] != '.': continue
            for n in range(1, 10):
                if self.isValid(i, j, n, board):
                    board[i][j] = str(n)
                    if self.solve(board):
                        return True
                    board[i][j] = '.'
            return False
    return True

def isValid(self, row, col, n, board):
    for i in range(9):
        b_row = (row//3) * 3 + i//3
        b_col = (col//3) * 3 + i%3
        if board[row][i] == str(n): return False
        if board[i][col] == str(n): return False
        if board[b_row][b_col] == str(n): return False
        
    return True