数独游戏 C++ 回溯法.doc

数独游戏 C++ 回溯法 　　数独游戏的规则： 　　1 每个数字在每一行只能出现一次 　　2 每个数字在每一列只能出现一次 　　3 每个数字在每一区只能出现一次 　　下面的input.txt是一个例子的约束条件 第一列表示每一个数所在的行 第二列表示每一个数所在的列，第三个这个位置上的值。 　　Input.txt 　　1 1 7 　　1 4 1 　　1 8 8 　　1 9 3 　　2 1 4 　　2 3 2 　　2 5 7 　　2 6 3 　　3 4 4 　　3 5 5 　　3 8 2 　　3 9 7 　　4 3 7 　　4 7 3 　　4 8 1 　　4 9 2 　　5 2 4 　　5 3 3 　　5 4 8 　　6 3 5 　　6 5 9 　　7 2 2 　　7 3 1 　　7 5 8 　　8 2 3 　　8 4 2 　　8 6 1 　　8 7 8 　　9 7 2 　　9 8 6 　　9 9 1 　　一 回溯法 　　//============================================ 　　#include 　　#include 　　using namespace std; 　　int State[9][9]; 　　///------------------------------ 　　void InitState() 　　{ 　　for (int i=0; i9; i++) 　　{ 　　for (int j=0; j9;j++) 　　{ 　　State[i][j] = 0; 　　} 　　} 　　} 　　//------------------------------- 　　void Load() 　　{ 　　freopen(input.txt,r,stdin); //输入从input.txt 　　int x, y, value; 　　int temp = 0; 　　while (scanf (%d %d %d, x, y, value) != EOF) 　　{ 　　State[x-1][y-1] = value; 　　} 　　} 　　//--------------------------------- 　　//检查每一个小区内只能出现一次 　　bool ChechZone(int x, int y, int i) 　　{ 　　int xZone = 3 * (x / 3); //找到每个小区的位置 　　int yZone = 3 * (y / 3); 　　int j = 0; 　　int k = 0; 　　bool flag = true; 　　for (j=xZone; j p 　　{ 　　for (k=yZone; k 　　{ 　　//if (x == j y == k) 　　//{ 　　// continue; 　　//} 　　if ((x != j || y != k) State[j][k] == i) 　　{ 　　flag = false; 　　goto A1; 　　} 　　} 　　} 　　A1: 　　return flag; 　　} 　　//-------------------------------- 　　//检查是否符合条件 　　bool ChechAssign(int x, int y, int i) 　　{ 　　bool flag = true; 　　for (int k=0; k9; k++) 　　{ 　　if (k != y i == State[x][k] ) 　　{ 　　flag = false; 　　} 　　if (k != x i == State[k][y] ) 　　{ 　　flag = false; 　　} 　　if (!ChechZone(x, y, i)) 　　{ 　　flag = false; 　　} 　　} 　　return flag; 　　} 　　///------------------------------ 　　int Search (int depth) 　　{ 　　if (depth = 81) 　　{ 　　//return Chech(); 　　return 1; 　　} 　　int x, y; 　　x = depth / 9 ; 　　y = depth % 9 ; 　　//检查x y有没有被 赋值 　　if (0 != State[x][y]) 　　{ 　　return Search (depth + 1); 　　} 　　else //尝试赋值 　　{ 　　for (int i=1; i=9; i++) 　　{ 　　//检查是否违反约束条件 　　State[x][y] = i; 　　if (ChechAss