> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/1-100/valid-sudoku.md).

# 36. Valid Sudoku

### Description

Determine if a 9x9 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 9 `3x3` sub-boxes of the grid must contain the digits `1-9` without repetition.

![A partially filled Sudoku which is valid.](https://1091135627-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MEmU-aGQcUvtjjAH8_3%2F-MF-Kw95_dKa58-cpUaL%2F-MF-LGQDSVactP4E-gaA%2Fimage.png?alt=media\&token=283cdd62-5c8b-4186-8ae8-dc974b31f3eb)

 The Sudoku board could be partially filled, where empty cells are filled with the character `'.'`.

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.

### Constraints

*  The given board contain only digits `1-9` and the character `'.'`
* The given board size is always `9x9`.

### Approach

### Links

* [GeeksforGeeks](https://www.geeksforgeeks.org/check-if-given-sudoku-board-configuration-is-valid-or-not/)
* [Leetcode](https://leetcode.com/problems/valid-sudoku/)
* ProgramCreek
* YouTube

### Examples

{% tabs %}
{% tab title="Example 1" %}
**Input:**

\[

\["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
{% endtab %}

{% tab title="Example 2" %}
**Input:**

\[

\["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.
{% endtab %}
{% endtabs %}

### Solutions

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(n*n)
 * Space complexity : O(n*n)
 */

class Solution {
    private static final int SIZE = 9;
    
    public boolean isValidSudoku(char[][] board) {
        Set<String> seen = new HashSet<>();
        for(int i = 0; i < SIZE; i++) {
            for(int j = 0; j < SIZE; j++) {
                char ch = board[i][j];
                if(ch != '.') {
                    if(!seen.add(ch + "-r-" + i) || 
                       !seen.add(ch + "-c-" + j) || 
                       !seen.add(ch + "-b-" + i/3 + "-" + j/3)) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private static final int SIZE = 9;
    
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i < SIZE; i++) {
            if(!(isValidRow(board, i) && isValidColumn(board, i))) return false;
        }
        for(int i = 0; i < SIZE; i += 3) {
            for(int j = 0; j < SIZE; j += 3) {
                if(!isValidBox(board, i, j)) return false;
            }
        }
        return true;
    }
    
    private boolean isValidRow(char[][] board, int row) {
        Set<Integer> rowValues = new HashSet<>();
        for(int i = 0; i < SIZE; i++) {
            int val = board[row][i]-'0';
            if(val == -2) continue;
            if(val < 1 || val > 9 || rowValues.add(val) == false) {
                return false;
            }
        }
        return true;
    }
    
    private boolean isValidColumn(char[][] board, int col) {
        Set<Integer> colValues = new HashSet<>();
        for(int i =0; i < SIZE; i++) {
            int val = board[i][col]-'0';
            if(val == -2) continue;
            if(val < 1 || val > 9 || colValues.add(val) == false) {
                return false;
            }
        }
        return true;
    }
    
    private boolean isValidBox(char[][] board, int row, int col) {
        Set<Integer> boxValues = new HashSet<>();
        for(int i = row; i < row+3; i++) {
            for(int j = col; j < col+3; j++) {
                int val = board[i][j]-'0';
                if(val == -2) continue;
                if(val < 1 || val > 9 || boxValues.add(val) == false) {
                    return false;
                }
            }
        }
        return true;
    }
}
```

{% endtab %}

{% tab title="Solution 3" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private static final int SIZE = 9;
    
    public boolean isValidSudoku(char[][] board) {
        boolean[][] rows = new boolean[SIZE][SIZE];
        boolean[][] cols = new boolean[SIZE][SIZE];
        boolean[][] boxes = new boolean[SIZE][SIZE];
        for(int i = 0; i < SIZE; i++) {
            for(int j = 0; j < SIZE; j++) {
                int num = board[i][j]-'1';
                if(num >= 0) {
                    int box_index = (i / 3) * 3 + j / 3;
                    if(rows[i][num] || cols[j][num] || boxes[box_index][num]) {
                        return false;
                    }
                    rows[i][num] = true;
                    cols[j][num] = true;
                    boxes[box_index][num] = true;   
                }
            }
        }
        return true;
    }
}
```

{% endtab %}

{% tab title="Solution 4" %}

```java
/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private static final int SIZE = 9;
    
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0; i < SIZE; i++) {
            boolean[] row = new boolean[SIZE];
            boolean[] col = new boolean[SIZE];
            boolean[] box = new boolean[SIZE];
            for(int j = 0; j < SIZE; j++) {
                int num = board[i][j]-'1';
                if(board[i][j] != '.') {
                    if(row[board[i][j]-'1']) return false;
                    row[board[i][j]-'1'] = true;
                }
                if(board[j][i] != '.') {
                    if(col[board[j][i]-'1']) return false;
                    col[board[j][i]-'1'] = true;
                }
                int boxi = (i/3)*3 + j/3;
                int boxj = (i%3)*3 + j%3;
                if(board[boxi][boxj] != '.') {
                    if(box[board[boxi][boxj]-'1']) return false;
                    box[board[boxi][boxj]-'1'] = true;
                }
            }
        }
        return true;
    }
}
```

{% endtab %}
{% endtabs %}

### Follow up

* Program for Sudoku Generator - [GFG](https://www.geeksforgeeks.org/program-sudoku-generator/)
* Validity of a given Tic-Tac-Toe board configuration - [GFG](https://www.geeksforgeeks.org/validity-of-a-given-tic-tac-toe-board-configuration/)