# 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**:

1. Each of the digits `1-9` must occur exactly once in each row.
2. Each of the digits `1-9` must occur exactly once in each column.
3. 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 `'.'`.

![](https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png)\
A sudoku puzzle...

![](https://upload.wikimedia.org/wikipedia/commons/thumb/3/31/Sudoku-by-L2G-20050714_solution.svg/250px-Sudoku-by-L2G-20050714_solution.svg.png)\
...and its solution numbers marked in red.

**Note:**

* The given board contain only digits `1-9` and the character `'.'`.
* You may assume that the given Sudoku puzzle will have a single unique solution.
* The given board size is always `9x9`.

分析

dfs或者brute force，就是对于每个格子，loop 1-9尝试放入，然后下一步dfs，可以就返回true，不可以就reset cell

**注意这里先check再放入，为了后面check方便,不污染原matrix**

string.digits去掉0，本身就是char，不需要str(i)

2种块坐标表达法

x,y都是到block的初始点，然后+offset 0-3

```
int row = i - i%3, column = j - j%3;
x,y range(3)
 if(board[row+x][column+y] == val) return false;
 
 i range(9)
 int blkrow = (row / 3) * 3, blkcol = (col / 3) * 3; 
 board[blkrow + i / 3][blkcol + i % 3] == num
```

```

class Solution:
    def solveSudoku(self, b: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        def check(i,j,c):
            brow = i - i%3 
            bcol = j - j%3
            for x in range(9):
                if b[i][x] == c or b[x][j] == c:
                    return False

            for x in range(3):
                for y in range(3):
                    if b[brow+x][bcol+y] == c:
                        return False
            return True 
        
        def dfs(i,j):
            if i == 9:
                return True
            if j == 9:
                return dfs(i+1,0)
            if b[i][j] !='.':
                return dfs(i,j+1)
            for c in string.digits:
                if c != '0' and check(i,j,c):
                    b[i][j] = c
                    if dfs(i,j+1):
                        return True
                    b[i][j]  = '.'
            return False
        dfs(0,0)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://nataliekung.gitbook.io/ladder_code/wish-1/sudoku-solver.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.