题目：
你一定听说过“数独”游戏。如【图1.png】，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个同色九宫内的数字均含1-9，不重复。数独的答案都是唯一的，所以，多个解也称为无解。本图的数字据说是芬兰数学家花了3个月的时间设计出来的较难的题目。但对会使用计算机编程的你来说，恐怕易如反掌了。本题的要求就是输入数独题目，程序输出数独的唯一解。我们保证所有已知数据的格式都是合法的，并且题目有唯一的解。格式要求，输入9行，每行9个数字，0代表未知，其它数字为已知。输出9行，每行9个数字表示数独的解。例如：输入（即图中题目）：005300000800000020070010500400005300010070006003200080060500009004000030000009700程序应该输出：145327698839654127672918543496185372218473956753296481367542819984761235521839764再例如，输入：800000000003600000070090200050007000000045700000100030001000068008500010090000400程序应该输出：812753649943682175675491283154237896369845721287169534521974368438526917796318452资源约定：峰值内存消耗 < 256MCPU消耗 < 2000ms请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意: main函数需要返回0注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。提交时，注意选择所期望的编译器类型。
//思路就是从右下角开始dfs，直到左上角结束，（左上角开始到右下角结束也可以）
#include <bits/stdc++.h> using namespace std; const int maxn = 20; const int INF = 0x3f3f3f3f; int G[maxn][maxn]; int cnt = 0;//数独种数 //一整行，一整列， bool vis_row[maxn][maxn], vis_column[maxn][maxn]; //对应9个块，序号（0-9）（包括0和8） bool vis_block[maxn][maxn][maxn];//表示该块中，某个数字(0-9)是否使用过 int Cal(int x, int y) { return min(min(x-0, 8-x), min(y-0, 8-y)) + 6; } void sign(int x, int y, int z, bool flag) { vis_row[x][z] = vis_column[y][z] = flag; vis_block[x/3][y/3][z] = flag; } bool check(int x, int y, int z) { if (vis_row[x][z]) { return false; } if (vis_column[y][z]) { return false; } if (vis_block[x/3][y/3][z]) { return false; } return true; } void dfs(int x, int y) { if (x == -1) { cnt++; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { cout << G[i][j]; } cout << endl; } cout << endl; return; } if (G[x][y]) { sign(x, y, G[x][y], true); if (y == 0) { dfs(x-1, 8); } else { dfs(x, y-1); } } else { for (int i = 1; i <= 9; i++) { if (!check(x, y, i)) { continue; } sign(x, y, i, true); G[x][y] = i; if (y == 0) { dfs(x-1, 8); } else { dfs(x, y-1); } sign(x, y, i, false); G[x][y] = 0; } } } int main() { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { scanf(" ", &G[i][j]);//读入一个位的数字 if (G[i][j]) { sign(i, j, G[i][j], true); } } } dfs(8, 8); cout << cnt << endl; return 0; }