简单的DFS,预处理优化了一下。

#include <algorithm>
#include
<iostream>
#include
<cstring>
#include
<vector>
#include
<string>

using namespace std;

const int N = 9;
int table[N][N] = {};
bool flag = false;

class Blank
{
public:
int row;
int column;
int num;
bool candidate[N + 1];
public:
Blank(
const int& x = 0, const int& y = 0): row(x), column(y), num(0)
{
memset(candidate,
false, sizeof(candidate));
}
bool operator < (const Blank& rOprand)
{
return this->num < rOprand.num;
}
};

vector
<Blank> candidateBlank;

bool isLegal(int x, int y, int key)
{
// 检查列
for (int i = 0; i < N; ++i)
if (table[i][y] == key)
return false;
// 检查行
for (int j = 0; j < N; ++j)
if (table[x][j] == key)
return false;
// 指向所在九宫格的左上角
int i = x / 3 * 3;
int j = y / 3 * 3;
// 检查所在的九宫格
for (int l = i; l < i + 3; ++l)
for (int s = j; s < j + 3; ++s)
if (table[l][s] == key)
return false;
return true;
}

void initCandidate()
{
for (int i = 0; i < (int)candidateBlank.size(); ++i)
{
for (int j = 1; j <= N; ++j)
{
if (isLegal(candidateBlank[i].row, candidateBlank[i].column, j))
{
candidateBlank[i].num
++;
candidateBlank[i].candidate[j]
= true;
}
}
}
sort(candidateBlank.begin(), candidateBlank.end());
}

void input()
{
flag
= false;
candidateBlank.clear();
for (int i = 0; i < N; ++i)
{
string temp;
cin
>> temp;
for (int j = 0; j < N; ++j)
{
table[i][j]
= temp[j] - '0';
if (table[i][j] == 0)
{
Blank temp(i, j);
candidateBlank.push_back(temp);
}
}
}
initCandidate();
}

void output()
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
cout
<< table[i][j];
cout
<< endl;
}
}

void DFS(const int& pos)
{
if (pos >= (int)candidateBlank.size())
{
flag
= true;
return;
}
for (int key = 1; key <= N; ++key)
{
if (candidateBlank[pos].candidate[key] &&
        isLegal(candidateBlank[pos].row, candidateBlank[pos].column, key))
{
table[candidateBlank[pos].row][candidateBlank[pos].column]
= key;
DFS(pos
+ 1);
if (flag) return;
table[candidateBlank[pos].row][candidateBlank[pos].column]
= 0;
}
}
}

void test()
{
input();
DFS(
0);
output();
}

int main()
{
int num;
cin
>> num;
while (0 != num--)
{
test();
}
system(
"pause");
}