[cpp]
#include <iostream>
#include <algorithm>
using namespace std;
int map[9][9];
bool isPlace(int count){
int row = count / 9;
int col = count % 9;
int j;
//同一行
for(j = 0; j < 9; ++j){
if(map[row][j] == map[row][col] && j != col){
return false;
}
}
//同一列
for(j = 0; j < 9; ++j){
if(map[j][col] == map[row][col] && j != row){
return false;
}
}
//同一小格
int tempRow = row / 3 * 3;
int tempCol = col / 3 * 3;
for(j = tempRow; j < tempRow + 3;++j){
for(int k = tempCol; k < tempCol + 3; ++k){
if(map[j][k] == map[row][col] && j != row && k != col){
return false;
}
}
}
return true;
}
void backtrace(int count){
if(count == 81){
cout<<"結果："<<endl;
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
cout<<map[i][j]<<" ";
}
cout<<endl;
}
return;
}
int row = count / 9;
int col = count % 9;
if(map[row][col] == 0){
for(int i = 1; i <= 9; ++i){
map[row][col] = i;//賦值 www.2cto.com
if(isPlace(count)){//可以放
backtrace(count+1);//進入下一層
}
}
map[row][col] = 0;//回溯
}else{
backtrace(count+1);
}
}
int main()
{
for(int i = 0; i < 9; ++i){
for(int j = 0; j < 9; ++j){
cin>>map[i][j];
}
}
backtrace(0);
return 0;
}
測試數據：
[plain]
8 0 0 0 0 0 0 0 1
9 0 0 0 2 0 0 0 3
0 3 0 0 5 0 0 7 0
0 0 5 0 0 0 4 0 0
0 0 4 5 0 9 6 0 0
0 0 0 8 0 1 0 0 0
0 0 0 0 0 0 0 0 0
0 4 6 0 0 0 8 2 0
0 2 0 3 0 5 0 9 0
運行結果：
