POJ - 2676 : http://poj.org/problem?id=2676:
解题思想 （大力出奇迹）：
1. 依次在空格里面填上“1~9”，并检查这个数字是否合法（其所在的行、列，以及3X3的子区域里不存在重复的数字）。如果合法，则前进到下一个格子。
2. 如果在某个格子里，从“1”到“9”都不合法，这说明前面某个格子填错了。这时就回退到上一格，继续试。例如，如果上一格已填的数字是3，就继续试4，5，6，… 是否合法。如果找到一个合法的数字，则又前进到下一格。如果找不到，说明前面还有格子也填错了，则继续回退到更前面一格，… 如此反复。
4. 如果这个数独是有解的，我们总会遇到“蒙对了”的情况。如果这个数独是没有解的，那么我们会遇到“第一个格子试了1~9所有的数字都不行”的情况。
这不是AC代码！这不是AC代码！这不是AC代码！，POJ目前停服了，输入格式需要改，但代码是正确的。
#include <iostream>
using namespace std; int M[][];
bool flag = false; int check(int row, int column, int x) {
for (int i = ; i < ; i++) {
if (M[i][column] == x || M[row][i] == x)
return ;
}
int r = row / * , c = column / * ;
for (int i = r; i < r + ; i++) {
for (int j = c; j < c + ; j++) {
if (M[i][j] == x) return ;
}
}
return ;
}
void DFS(int row, int column) {
if (row == ) {
flag = true;
return;
} if (M[row][column] == ) {
int i;
for (i = ; i <= ; i++) {
if (check(row, column, i)) {
M[row][column] = i;
DFS(row + (column + ) / , (column + ) % );
if (flag)
return;
}
}
if (i == ) {
//这里回溯，赋值0是为了下次继续赋值
M[row][column] = ;
return;
}
}
//DFS((row + 1) % 9, column+(row+1)/9);
DFS(row + (column + ) / , (column + ) % );
}
int main() {
int i = ;
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
cin >> M[i][j];
}
}
DFS(, );
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
cout << M[i][j] << " ";
}
cout << endl;
}
return ;
}