# 0036. Valid Sudoku

https://leetcode.com/problems/valid-sudoku

## Description

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 `'.'`.

## ac1: HashSet

`set.add()` will return boolean, to make your code consise

```java
class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 3 set: horizontal, vertical, matrix
        List<Set<Character>> hori = new ArrayList<Set<Character>>();
        List<Set<Character>> verti = new ArrayList<Set<Character>>();
        for (int i = 0; i < 9; i++) {
            hori.add(new HashSet<Character>());
            verti.add(new HashSet<Character>());
        }

        List<List<Set<Character>>> matr = new ArrayList<List<Set<Character>>>();
        for (int i = 0; i < 3; i++) {
            List<Set<Character>> tmp = new ArrayList<Set<Character>>();
            tmp.add(new HashSet<Character>());
            tmp.add(new HashSet<Character>());
            tmp.add(new HashSet<Character>());
            matr.add(tmp);
        }

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') continue;

                if (hori.get(r).contains(board[r][c])){
                    return false;
                } else {
                    hori.get(r).add(board[r][c]);
                }

                if (verti.get(c).contains(board[r][c])){
                    return false;
                } else {
                    verti.get(c).add(board[r][c]);
                }

                if (matr.get(r/3).get(c/3).contains(board[r][c])) return false;
                else matr.get(r/3).get(c/3).add(board[r][c]);
            }
        }

        return true;
    }
}
```

## ac2: boolean\[]\[]

faster and concise

```java
class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 3 boolean matrix
        // check current char is used or not
        boolean[][] hori = new boolean[9][10];
        boolean[][] verti = new boolean[9][10];
        boolean[][] cube = new boolean[9][10];

        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') continue;
                int val = board[r][c] - '0';
                int cubeIdx = (r/3) * 3 + c/3;

                if (hori[r][val] || verti[c][val] || cube[cubeIdx][val]) return false;
                hori[r][val] = true;
                verti[c][val] = true;
                cube[cubeIdx][val] = true;
            }
        }

        return true;
    }
}
```
