本文链接:http://i.cnblogs.com/EditPosts.aspx?postid=5398818
题意：
给你一个 9*9 的矩阵，同一行相邻的两个元素用一个空格分开。其中1-9代表该位置的已经填好的数，问号（?）表示需要你填的数。输出这个数独的解，每组有且只有一个解。
思路：
记录下空缺的地方，每个空缺的地方有 9 中状态，DFS + 剪枝处理其他的，用scanf进行输入，gets() TLE到死。。。。
代码：
#include <cstdio> #include <iostream> #include <cstring> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> using namespace std; const int MAXN = 11; int Gra[MAXN][MAXN];//存放 9 * 9 的大格局 int Ans[83]; //存放 空缺的、要填数的 位置的 一种映射 (i - 1 ) * 9 + j int rowLine[11][11]; //rowLine[ z = (i - 1) / 3 * 3 + (j - 1) / 3 ][k]表示 第 z(0 1 2 3 4 5 6 7 8) 个格子中 k 数字是否出现过(0 / 1) int line[11][11]; // line[i][k] 表示 第 i 行 k 这个数字是否出现过 int row[11][11]; //row[j][k] 表示 第 j 列 k 这个数字是否出现过 int N; //要填数的格子的总数 int getX(int k) //根据存放空缺位置的数组的第k个数反推出坐标 X { return (Ans[k] - 1) / 9 + 1; } int getY(int k) //根据存放空缺位置的数组的第k个数反推出坐标 Y { return Ans[k] % 9 == 0 ? 9 : Ans[k] % 9; } void deal(int i, int j, int k, int num) //在 Gra(i, j)位置 放k(num = 1)/移走k(num = -1) 时需要维护用于标记是否重复的数组 { line[i][ k ] += num; //维护行数组 row[j][ k ] += num; //维护列数组 rowLine[(i - 1) / 3 * 3 + (j - 1) / 3 ][k] += num; //维护 标记 3 * 3 的数组 } int check(int k, int n) //判断在 第 n 个空缺的地方放置 k 是否合法 { int x = getX(n); int y = getY(n); if(line[x][k] == 1) return 0; //同一行有重复的 if(row[y][k] == 1) return 0; //同一列有重复的 if(rowLine[ (x - 1) / 3 * 3 + (y - 1) / 3 ][k] == 1) return 0; //同一个 3 * 3的方格子里有重复的 return 1; } void pf() { for(int i = 1; i <= 9; i++) { for(int j = 1; j <= 9; j++) printf(j == 1 ? "%d":" %d",Gra[i][j]); cout <<endl; } } int flag; void backtrack(int k) { if( k > N ){pf();flag = 1;return;} for(int i = 1; i <= 9; i++) //每一个 空缺的位置都有 9 种填法(状态) { int x = getX(k);int y = getY(k); if(check(i, k)) //判断合法性 { Gra[ x ][ y ] = i; deal(x, y, i, 1); //由于新加入的数 所以需要维护 标志的数组 backtrack( k + 1); //if(flag )return; deal(x, y, i, -1); //恢复现场 Gra[ x ][ y ] = 0; } } } //初始化 void init() { N = 0; flag = 0; memset(Gra, -1, sizeof(Gra)); memset(rowLine, 0, sizeof(rowLine)); memset(Ans, 0, sizeof(Ans)); memset(line, 0, sizeof(line)); memset(row, 0, sizeof(row)); } int main() { //freopen("in.txt", "r", stdin); char s[3]; int ln = 0; while(~scanf("%s",s)) { if(ln++)printf(" "); init(); if(s[0] == '?'){Gra[1][1] = 0; Ans[++N] = 1;} else{ Gra[1][1] = s[0] - 48; deal(1 , 1, Gra[1][1], 1);} for(int i = 0; i < 9; i++) { for(int j = 0; j < 9; j++) { if(i == 0 && j == 0)continue; scanf("%s",s); if(s[0] == '?'){Gra[i + 1][j + 1] = 0; Ans[++N] = i * 9 + j + 1;} else{ Gra[i + 1][j + 1] = s[0] - 48; deal(i + 1 , j + 1, Gra[i + 1][j + 1], 1);} } } flag = 0; backtrack(1); } return 0; }