> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/array/sudoku.md).

# 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

```python
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

```python
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
```