判断valid，没有更好的方法，只能brute force。
class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
int n;
for (int i = ; i < ; ++i) {
vector<bool> contained(, false);
for (int j = ; j < ; ++j) {
if (board[i][j] == '.') continue;
n = board[i][j] - '' - ;
if (contained[n]) return false;
contained[n] = true;
}
}
for (int i = ; i < ; ++i) {
vector<bool> contained(, false);
for (int j = ; j < ; ++j) {
if (board[j][i] == '.') continue;
n = board[j][i] - '' - ;
if (contained[n]) return false;
contained[n] = true;
}
}
for (int i = ; i < ; ++i) {
for (int j = ; j < ; ++j) {
vector<bool> contained(, false);
for (int k = ; k < ; ++k) {
for (int m = ; m < ; ++m) {
if (board[i*+k][j*+m] == '.') continue;
n = board[i*+k][j*+m] - '' - ;
if (contained[n]) return false;
contained[n] = true;
}
}
}
}
return true;
}
};
求解决方案也只有backtrack。
class Solution {
public:
void solveSudoku(vector<vector<char> > &board) {
list<int> unsolved;
getUnsolved(board, unsolved);
recursive(board, unsolved);
}
bool recursive(vector<vector<char> > &board, list<int> &unsolved) {
if (unsolved.empty()) return true;
int loc = unsolved.front();
int row = loc / ;
int col = loc % ;
vector<bool> contained(, false);
int n;
for (int i = ; i < ; ++i) {
if (board[row][i] != '.') {
contained[board[row][i] - '' - ] = true;
}
if (board[i][col] != '.') {
contained[board[i][col] - '' - ] = true;
}
}
row = row / ; col = col / ;
for (int i = ; i < ; ++i) {
for (int j = ; j < ; ++j) {
if (board[row * + i][col * + j] != '.') {
contained[board[row * + i][col * + j] - '' - ] = true;
}
}
}
row = loc / ; col = loc % ;
for (int i = ; i < ; ++i) {
if (!contained[i]) {
board[row][col] = i + + '';
unsolved.pop_front();
if (recursive(board, unsolved)) return true;
board[row][col] = '.';
unsolved.push_front(loc);
}
}
return false;
}
void getUnsolved(vector<vector<char> > &board, list<int> &unsolved) {
for (int i = ; i < ; i++) {
for (int j = ; j < ; ++j) {
if (board[i][j] == '.') {
unsolved.push_back(i * + j);
}
}
}
}
};
用unsolved数组可以避免每次都需要从头扫到尾去找下一个元素。
用contained数组先保存了在该行该格该九宫格里已经存在的数字。这样就可以直接去试验剩下的数字，而不需要每次都再检查一遍插入的值是否合法。
backtrack是一个要有返回值，否则都不知道你backtrack到头了没，是否找到解决方案了。