# Valid Sudoku

## Question

Determine whether a Sudoku is valid.

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

Example
The following partially filed sudoku is valid.


Valid Sudoku

Note
A valid Sudoku board (partially filled) is not necessarily solvable.
Only the filled cells need to be validated.
Clarification
What is Sudoku?

http://sudoku.com.au/TheRules.aspx
https://zh.wikipedia.org/wiki/%E6%95%B8%E7%8D%A8
https://en.wikipedia.org/wiki/Sudoku
http://baike.baidu.com/subview/961/10842669.htm


## 题解

### Java

class Solution {
/**
* @param board: the board
@return: wether the Sudoku is valid
*/
public boolean isValidSudoku(char[][] board) {
if (board == null || board.length == 0) return false;

// check row
for (int i = 0; i < 9; i++) {
boolean[] numUsed = new boolean[9];
for (int j = 0; j < 9; j++) {
if (isDuplicate(board[i][j], numUsed)) {
return false;
}
}
}

// check column
for (int i = 0; i < 9; i++) {
boolean[] numUsed = new boolean[9];
for (int j = 0; j < 9; j++) {
if (isDuplicate(board[j][i], numUsed)) {
return false;
}
}
}

// check sub box
for (int i = 0; i < 9; i = i + 3) {
for (int j = 0; j < 9; j = j + 3) {
if (!isValidBox(board, i, j)) {
return false;
}
}
}

return true;
}

private boolean isValidBox(char[][] box, int x, int y) {
boolean[] numUsed = new boolean[9];
for (int i = x; i < x + 3; i++) {
for (int j = y; j < y + 3; j++) {
if (isDuplicate(box[i][j], numUsed)) {
return false;
}
}
}
return true;
}

private boolean isDuplicate(char c, boolean[] numUsed) {
if (c == '.') {
return false;
} else if (numUsed[c - '1']) {
return true;
} else {
numUsed[c - '1'] = true;
return false;
}
}
}


## Reference

• Soulmachine 的 leetcode 题解