判断一个数独是否合法，未填的空格用字符 ' . ' 表示。该数独有解并不是必要的。
e.g. 如图合法数独，输入
["53..7....","6..195...",".98....6.","8...6...3","4..8.3..1","7...2...6",".6....28.","...419..5","....8..79"]
返回 true。
我依然使用死办法解决，而且进行了输入合法性判断，即必须为 1 ~ 9 的数字或 ' . ' 。
bool isValidSudoku(vector<vector<char>>& board) {
vector<char> row, column, subbox;
for (int i = ; i < ; ++i) {
row.clear();
column.clear();
row = board[i];
if (!isValid(row))
return false;
for (int j = ; j < ; ++j) {
column.push_back(board[j][i]);
}
if (!isValid(column))
return false;
}
for (int i = ; i <= ; i = i + ) {
for (int j = ; j <= ; j = j + ) {
subbox.clear();
subbox.push_back(board[i][j]); subbox.push_back(board[i][j+]); subbox.push_back(board[i][j+]);
subbox.push_back(board[i+][j]); subbox.push_back(board[i+][j+]); subbox.push_back(board[i+][j+]);
subbox.push_back(board[i+][j]); subbox.push_back(board[i+][j+]); subbox.push_back(board[i+][j+]);
if (!isValid(subbox))
return false;
}
}
return true;
}
bool isValid(vector<char> &t) {
sort(t.begin(), t.end());
for (int i = ; i < ; ++i) {
if (((t[i] < '' || t[i] > '') && t[i] != '.') || (i > && t[i] == t[i - ] && t[i] != '.'))
return false;
}
return true;
}
答案巧妙的做法如下
bool isValidSudoku(vector<vector<char>>& board) {
bool row[][] = {false}, col[][] = {false}, box[][] = {false};
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
if (board[i][j] != '.') {
int num = board[i][j] - '' - , k = i / * + j / ;
if (row[i][num] || col[j][num] || box[k][num]) return false;
row[i][num] = col[j][num] = box[k][num] = true;
}
}
}
return true;
}
num = board[i][j] - '0' - 1 的思路就是用一个新 bool 型数组（初始化全为 false）判断原数组是否有重复元素。
k = i / 3 * 3 + j / 3 将原来 9 * 9 的方格映射到 3 * 3 的方格中！
0 | 1 | 2
3 | 4 | 5
6 | 7 | 8
例如 i = 5，j = 6 （第 5 行 第 6 列）时，k = 5 / 3 * 3 + 6 / 3 = 1 * 3 + 2 = 5，在 box[5][] 这个数组里进行判断。
这种方法更常规的用法见下。
这个Java实现也很巧妙
public boolean isValidSudoku(char[][] board) {
for(int i = 0; i < 9; i++) {
Set<Character> rows = new HashSet<>();
Set<Character> cols = new HashSet<>();
Set<Character> cubes = new HashSet<>();
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.' && !rows.add(board[i][j])) return false;
if (board[j][i] != '.' && !cols.add(board[j][i])) return false;
int colStart = 3 * (i % 3), rowStart = 3 * (i / 3);
int colOffset = j % 3, rowOffset = j / 3; // 偏移
int row = rowStart + rowOffset, col = colStart + colOffset;
if (board[row][col] != '.' && !cubes.add(board[row][col]) ) return false;
}
}
return true;
}
HashSet 的 add(E e) 方法用于将指定元素添加到这个 HashSet，若此 Set 已经包含该元素，则直接返回 false。
% 和 / 操作符对于矩阵遍历问题很有帮助。
使用 % 作水平遍历，即计算列坐标偏移。因为 j 每增加 ，j % 3 也增加 然后重置。
使用 / 作竖直遍历，即计算行坐标偏移。因为 j 每增加 ，j / 3 才能增加 。
通过 0 ~ 8 的 j 即可遍历一个 9 * 9 矩阵的一个 3 * 3 子块。如何继续遍历下一个子块呢？就需要用外层循环 0 ~ 8 的 i 实现。
依然使用 % 水平遍历到下一个子块，colStart = 3 * (i % 3) ，× 3 是因为下一个子块在 3 列之后，第一个子块的起始是 (0, 0)，第二个子块的起始是 (0, 3) 而不是 (0, 1)。
e.g.
i = 2 时，j 从 0 ~ 8，
rowStart = 3 * (2 / 3) = 0 colStart = 3 * (2 % 3) = 6
rowOffset = j / 3 = 0,0,0, 1,1,1, 2,2,2 colOffset = j % 3 = 0,1,2, 0,1,2, 0,1,2
对应了 board 矩阵中的
| (0+0, 6+0) | (0+0, 6+1) | (0+0, 6+2) |
| (0+1, 6+0) | (0+1, 6+1) | (0+1, 6+2) |
| (0+2, 6+0) | (0+2, 6+1) | (0+2, 6+2) |
即
| (0,6) | (0,7) | (0,8) |
| (1,6) | (1,7) | (1,8) |
| (2,6) | (2,7) | (2,8) |
这个 Sub-Box。