Valid Sudoku
最后更新于：2022-04-02 01:14:20
# Valid Sudoku
### Source
- leetcode: [Valid Sudoku | LeetCode OJ](https://leetcode.com/problems/valid-sudoku/)
- lintcode: [(389) Valid Sudoku](http://www.lintcode.com/en/problem/valid-sudoku/)
~~~
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 题解
';