题目描述
Determine if a 9x9 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 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
Example1:
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
Example2:
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-9 and the character ‘.’.
- The given board size is always 9x9.
解题思路
- 首先要理解清题意 这里的数独并没有说必须要有解
- 只是说 给出的数独是否有效
- 我们可以用三个bool数组 来代表 在当前行，当前列，当前格子里是否有重复值
- 当前行 即 row[i][data]
- 当前列 即 col[data][j] // data[4][3] data[5][3] 表示第三列中有数字4 和 5
- 当前单元格子 cell[3 * (i / 3) + j / 3][data] // 第一个元素 表示第几个格子 第二个元素表示具体的数值
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<vector<bool>> row(9, vector<bool>(9));
vector<vector<bool>> col(9, vector<bool>(9));
vector<vector<bool>> cell(9, vector<bool>(9));
for(int i = 0; i < board.size(); i++){
for(int j = 0; j < board[0].size(); j++){
if(board[i][j] == '.'){
continue;
}
int c = board[i][j] - '1';
if(row[i][c] || col[c][j] || cell[3 * (i / 3) + j / 3][c]){
return false;
}
row[i][c] = true;
col[c][j] = true;
cell[3 * (i / 3) + j / 3][c] = true;
}
}
return true;
}
};
