題目
Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'
.
You may assume that there will be only one unique solution.
A sudoku puzzle...
...and its solution numbers marked in red.
分析
一開始想通過推理得到，希望通過數(shù)獨(dú)的規(guī)則得到每個(gè)空白格子可能的取值梗醇，然后往只有一種可能取值的格子填入該值。但是發(fā)現(xiàn)這樣不能得到最終結(jié)果温鸽。因?yàn)橥评淼倪^程實(shí)際上要使用三種方法手负。這就使得算法變得很復(fù)雜涤垫。
另一個(gè)思路是使用搜索蝠猬，但是直接搜索恐怕需要花費(fèi)高昂的代價(jià)统捶。
不過看題解是通過填入一個(gè)數(shù)字敦姻，然后使用第36題中的方法來判斷是否合法來確定是否繼續(xù)歧杏。這樣其實(shí)不需要搜索完整個(gè)空間犬绒，可以不超時(shí)完成。
實(shí)現(xiàn)一
class Solution {
public:
bool solveSudoku(vector<vector<char>>& board) {
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
if(board[i][j]!='.')
continue;
for(int num=0; num<9; num++){
board[i][j] = num + '0' + 1;
if(isValidSudoku(board) && solveSudoku(board))
return true;
board[i][j] = '.';
}
return false;
}
}
return true;
}
private:
bool isValidSudoku(vector<vector<char>>& board) {
for(int i=0; i<9; i++){
int trow[9]={0}, tcol[9]={0}, tblk[9]={0};
for(int j=0; j<9; j++){
if(board[i][j]!='.'){
int nrow = board[i][j] - '0' - 1;
if(trow[nrow]) return false;
trow[nrow]++;
}
if(board[j][i]!='.'){
int ncol = board[j][i] - '0' - 1;
if(tcol[ncol]) return false;
tcol[ncol]++;
}
int x = i / 3 * 3 + j / 3;
int y = i % 3 * 3 + j % 3;
if(board[x][y]!='.'){
int nblk = board[x][y] - '0' - 1;
if(tblk[nblk]) return false;
tblk[nblk]++;
}
}
}
return true;
}
};
思考一
這種方法雖然可行，而且簡單礼华，但是實(shí)在是太暴力了。所以想到把搜索和推理結(jié)合圣絮，以此來進(jìn)行剪枝的方法。具體就是記錄每一行捧请、每一列以及每一個(gè)方塊中未出現(xiàn)的數(shù)字棒搜，搜索時(shí)只搜索其允許的取值。另外還可以使用二進(jìn)制中的每一位來表示每一個(gè)數(shù)字是否被使用可款。
實(shí)現(xiàn)二
class Solution {
public:
int row[9], col[9], blo[9];
void solveSudoku(vector<vector<char>>& board) {
for(int i=0; i<9; i++){
row[i] = (1<<9) - 1;
col[i] = (1<<9) - 1;
blo[i] = (1<<9) - 1;
}
for(int i=0; i<9; i++){
for(int j=0; j<9; j++){
if(board[i][j]!='.'){
int num = board[i][j] - '1';
row[i] -= 1<<num;
col[j] -= 1<<num;
blo[i/3*3 + j/3] -= 1<<num;
}
}
}
dfs(0, 0, board);
}
private:
bool dfs(int x, int y, vector<vector<char>>& board){
if(y>8){
if(x<8){
y = 0;
x++;
}
else
return true;
}
if(board[x][y]!='.')
return dfs(x, y+1, board);
int tmp = row[x] & col[y] & blo[x/3*3 + y/3];
if(tmp==0)
return false;
for(int i=0; i<9; i++){
if(!(tmp & (1<<i)))
continue;
board[x][y] = i + '1';
row[x] -= 1<<i;
col[y] -= 1<<i;
blo[x/3*3 + y/3] -= 1<<i;
if(dfs(x, y+1, board))
return true;
board[x][y] = '.';
row[x] += 1<<i;
col[y] += 1<<i;
blo[x/3*3 + y/3] += 1<<i;
tmp -= 1<<i;
}
return false;
}
};
思考二
這個(gè)算法與上一個(gè)相比闺鲸，大大縮短了運(yùn)行時(shí)間陨舱。很值得參考。
需要注意的是游盲，使用位運(yùn)算時(shí)要注意運(yùn)算優(yōu)先級，位移操作的優(yōu)先級是很低的益缎，記得加括號。我才不會說我因?yàn)橥浖永ㄌ杁ebug了好久呢欣范。
