Determine if a 9×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-9without repetition. - Each column must contain the digits
1-9without repetition. - Each of the 9
3x3sub-boxes of the grid must contain the digits1-9without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
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
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.
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.
- The given board contain only digits
1-9and the character'.'. - The given board size is always
9x9.
判断一个数独棋盘是否合法，即每行每列和每个小方格内不能有’1’~’9’的重复数字。只要求检查是否合法，不要求棋盘是否可解，所以程序很简单，直接按行、列和小方格检查即可。 完整代码如下：
class Solution {
public:
bool isValidSudoku(vector<vector<char> >& board)
{
int m = board.size();
if (m != 9)
return false;
for (int i = 0; i < m; i++) { // 行
int n = board[i].size();
if (n != 9)
return false;
vector<int> rows(n, 0);
for (int j = 0; j < n; j++) {
if (board[i][j] != ‘.’) {
rows[board[i][j] – ‘1’]++;
if (rows[board[i][j] – ‘1’] > 1)
return false;
}
}
}
for (int j = 0; j < m; j++) { //列
vector<int> cols(m, 0);
for (int i = 0; i < m; i++) {
if (board[i][j] != ‘.’) {
cols[board[i][j] – ‘1’]++;
if (cols[board[i][j] – ‘1’] > 1)
return false;
}
}
}
for (int i = 0; i < m; i += 3) { // 小方格
for (int j = 0; j < m; j += 3) {
vector<int> cubes(m, 0);
for (int k = 0; k < m; k++) {
if (board[i + k / 3][j + k % 3] != ‘.’) {
cubes[board[i + k / 3][j + k % 3] – ‘1’]++;
if (cubes[board[i + k / 3][j + k % 3] – ‘1’] > 1)
return false;
}
}
}
}
return true;
}
};本代码提交AC，用时12MS。
上述代码不够简洁，其实可以只用一个循环把行、列、小方块判断了，参考：https://discuss.leetcode.com/topic/8241/my-short-solution-by-c-o-n2。
完整代码如下，i,j,k分别代表行号、列号、所在小方块的编号，用二维数组rows,cols,cubes标记是否重复。
class Solution {
public:
bool isValidSudoku(vector<vector<char> >& board)
{
int m = 9;
vector<vector<int> > rows(9, vector<int>(9, 0)), cols(9, vector<int>(9, 0)), cubes(9, vector<int>(9, 0));
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (board[i][j] != ‘.’) {
int num = board[i][j] – ‘0’ – 1;
int k = i / 3 * 3 + j / 3;
if (rows[i][num] > 0 || cols[j][num] > 0 || cubes[k][num] > 0)
return false;
rows[i][num] = cols[j][num] = cubes[k][num] = 1;
}
}
}
return true;
}
};本代码提交AC，用时12MS。
二刷。也是一次循环搞定行、列、和小方块，代码如下。这里面的i,j在检查行时，i是行号，j是列号；在检查列时，i是列号，j是行号；在检查小方块时，i是9个小方块在整个board中的编号，j是小方块内部每个格子的编号，都是从左往右，从上往下开始编号。
class Solution {
public:
bool IsRepeat(vector<int>& flag, char c) {
if (c == '.')return false;
int val = c - '0';
if (flag[val] > 0)return true;
++flag[val];
return false;
}
bool isValidSudoku(vector<vector<char>>& board) {
vector<int> row_flag(10, 0), col_flag(10, 0), box_flag(10, 0);
for (int i = 0; i < 9; ++i) {
fill(row_flag.begin(), row_flag.end(), 0);
fill(col_flag.begin(), col_flag.end(), 0);
for (int j = 0; j < 9; ++j) {
int box_row_start = i / 3 * 3, box_col_start = i % 3 * 3;
int box_row_offset = j / 3, box_col_offset = j % 3;
int box_row = box_row_start + box_row_offset, box_col = box_col_start + box_col_offset;
if ((box_row == 0 && (box_col == 0 || box_col == 3 || box_col == 6)) ||
(box_row == 3 && (box_col == 0 || box_col == 3 || box_col == 6)) ||
(box_row == 6 && (box_col == 0 || box_col == 3 || box_col == 6)))fill(box_flag.begin(), box_flag.end(), 0); // 小方块左上角
char rowc = board[i][j], colc = board[j][i], boxc = board[box_row][box_col];
if (IsRepeat(row_flag, rowc) || IsRepeat(col_flag, colc) || IsRepeat(box_flag, boxc))return false;
}
}
return true;
}
};本代码提交AC，用时12MS。