# Valid Sudoku

## Problem

Determine if a 9 x 9 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 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:

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

The algorithm is simple. The difficulty with this problem is managing complexity.

There are more terse solutions, but they are harder to understand. I think my solution is easy to understand, though it could be simplified e.g. by using Java streams or the standard library’s `unique`

function.

Because the size of the input is fixed to a 9x9 board, the time and space complexity is O(1).

```
class Solution {
public boolean isValidSudoku(char[][] board) {
// check rows
for (var i = 0; i < board.length; i++) {
if (unique(board[i])) {
continue;
} else {
return false;
}
}
// check cols
for (var i = 0; i < board.length; i++) {
var col = col(board, i);
if (unique(col)) {
continue;
} else {
return false;
}
}
// check blocks
for (var x = 0; x < 3; x++) {
for (var y = 0; y < 3; y++) {
var block = block(board, x, y);
if (unique(block)) {
continue;
} else {
return false;
}
}
}
return true;
}
// convert a block into an array
public char[] block(char[][] board, int x, int y) {
var offsetX = x * 3;
var offsetY = y * 3;
var boundX = offsetX + 3;
var boundY = offsetY + 3;
var block = new char[9];
var i = 0;
for (var cx = offsetX; cx < boundX; cx++) {
for (var cy = offsetY; cy < boundY; cy++) {
block[i] = board[cx][cy];
i += 1;
}
}
return block;
}
// convert a col into an array
public char[] col(char[][] board, int n) {
var col = new char[board.length];
// iterate over every row, grab the nth char
for (var i = 0; i < board.length; i++) {
col[i] = board[i][n];
}
return col;
}
public boolean unique(char[] c) {
var set = new HashSet<Character>();
for (var i = 0; i < c.length; i++) {
if (c[i] == '.') {
continue;
}
if (set.contains(c[i])) {
return false;
}
set.add(c[i]);
}
return true;
}
}
```