> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/6.array/36.-valid-sudoku-m.md).

# 36. Valid Sudoku (M)

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

1. Each row must contain the digits `1-9` without repetition.
2. Each column must contain the digits `1-9` without repetition.
3. Each of the nine `3 x 3` sub-boxes of the grid must contain the digits `1-9` without repetition.

**Note:**

* A Sudoku board (partially filled) could be valid but is not necessarily solvable.
* Only the filled cells need to be validated according to the mentioned rules.

 

**Example 1:**

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

```
Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true
```

**Example 2:**

```
Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
```

 

**Constraints:**

* `board.length == 9`
* `board[i].length == 9`
* `board[i][j]` is a digit `1-9` or `'.'`.

### **Solution:**

<https://www.jiuzhang.com/problem/valid-sudoku/><br>

#### 解题思路

这题考查的是二维数组的遍历顺序。

判断每一行是否合法，外层循环枚举行，内层循环枚举列。

判断每一列是否合法，外层循环枚举列，内层循环枚举行。

判断每一块是否合法，每一块左上角的坐标都是`(0, 0), (3, 0), (6, 0), (3, 0), (3, 3) ...`，可以发现都是`3`的倍数，可以总结出规律，先枚举`i = [0, 1, 2]，再枚举j = [0, 1, 2]`，左上角坐标就是`(i**3, j****3)`。

#### 代码思路

利用一个`set`来记录已经被用过的数，每次遍历一行，一列，一块，将访问过的元素加入`set`，冲突的话，返回`false`退出。最后返回`true`。

#### 复杂度分析

假设这是一个`N * N`的数独，不止是`9 * 9`。

**时间复杂度**

* 要遍历`3`次这个数独，时间复杂度为`O(N^2)`。

**空间复杂度**

* 需要`O(N)`的空间，记录以用过的数。

#### 源代码

javac++python

```
public class Solution {
    /**
     * @param board: the board
     * @return: whether the Sudoku is valid
     */
    public boolean isValidSudoku(char[][] board) {
        Set<Character> used = new HashSet();
        // 先枚举行，检查每行是否合法
        for (int row = 0; row < 9; row++) {
            used.clear();
            for (int col = 0; col < 9; col++) {
                if (! checkValid(board[row][col], used)) {
                    return false;
                }
            }
        }
        // 先枚举列，检查每列是否合法
        for (int col = 0; col < 9; col++) {
            used.clear();
            for (int row = 0; row < 9; row++) {
                if (! checkValid(board[row][col], used)) {
                    return false;
                }
            }
        }
        // 每个分块的左上角的坐标为(i * 3, j * 3)
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                used.clear();
                for (int row = i * 3; row < i * 3 + 3; row++) {
                    for (int col = j * 3; col < j * 3 + 3; col++) {
                        if (! checkValid(board[row][col], used)) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
    // 检查字符是否有冲突
    boolean checkValid(char c, Set<Character> used) {
        if (c == '.') {
            return true;
        }
        if (used.contains(c)) {
            return false;
        }
        used.add(c);
        return true;
    }
}
```