数独游戏C++回溯法

1、in doc .in数独游戏C+回溯法数独游戏的规则:1每个数字在每一行只能出现一次2每个数字在每一列只能出现一次3每个数字在每一区只能出现一次下面的input.txt是一个例子的约束条件第一列表示每一个数所在的行 第二列表示每一个数所在的列，第三个这个位置上的值。In put.txt旷doG in银豆网文章内容版权归原作者所有VICHU.NET19 321 42 3 22 5 726 334 43 5 53 8 239 743 74 7 3旷doG in银豆网4 8 149 252 45 3 354 863 565 972 27 3 175 882 3旷doG in银豆网in doc .in

2、回溯法/=#in elude#in eludeusing n amespace std;旷doG in银豆网文章内容版权归原作者所有VICHU.NETin doc .in旷doG in银豆网文章内容版权归原作者所有VICHU.NETint State99;IIIvoid Ini tState()for (i nt i=0; i9; i+)for (i nt j=0; j9;j+)Stateij = 0;in doc .in/void Load()freopen(input.txt,r,stdin); /输入从 input.txtint x, y, value;int temp = 0;whil

3、e (scanf (%d %d %d, &x, &y, &value) != EOF)Statex-1y-1 = value;/检查每一个小区内只能出现一次bool ChechZ on e(i nt x, int y, int i)int xZo ne = 3 * (x / 3); /找到每个小区的位置int yZone = 3 * (y / 3);int j = 0;int k = 0;bool flag = true;for (j=xZ on e; jfor (k=yZ one; k/if (x = j & y = k)/ con ti nue;/if (x != j | y != k)

4、& Statejk = i)flag = false;goto A1; doc in银豆网文章内容版权归原作者所有VICHU.NETin doc .inA1:retur n flag;/检查是否符合条件bool ChechAssig n(i nt x, int y, int i)bool flag = true;旷doG in银豆网文章内容版权归原作者所有VICHU.NETfor (int k=0; k= 81)/return Chech();return 1;int x, y;x = depth / 9 ;y = depth % 9 ;/检查x y有没有被赋值if (0 != Statexy

5、)return Search (depth + 1);else /尝试赋值for (i nt i=1; i=9; i+)/检查是否违反约束条件Statexy = i;if (ChechAssig n(x, y, i)if (Search(depth + 1)return 1;Statexy = 0;return 0;/void OutputState()for (i nt i=0; i9; i+)doc in银豆网文章内容版权归原作者所有VICHU.NETin doc .infor (i nt j=0; j9; j+)cout Stateij if (0 = (j+1) % 3)cout if

6、 (0 = (i + 1) % 3)doG in银豆网文章内容版权归原作者所有VICHU.NETcout en dl;cout en dl;cout en dl;/int mai n ()cout =初始化= endl en dl;Ini tState();/输入函数Load();OutputState();cout 结果为 endl en dl;/搜索if (Search(O)OutputState();elsein doc .in/输出提示信息cout 搜索失败川vv endl;cout = endl en dl;return 0;优化后的回溯就是先排序后再回溯 排序的依据是：先算出第一个

7、空格的所在行各所 在列对他的约束的个数。然后从大到小进行排序。优化后的程序如下:#in elude#in eludeusing n amespace std;/记录每个空元素的所在行列已有的数字个数int State99;int StateSort813; /非空元素为0void Prin t()for (i nt i=0; i81; i+)for (i nt j=0; j3; j+)cout StateSortij cout en dl;IIIvoid Ini tState()int i, j;旷doG in银豆网文章内容版权归原作者所有VICHU.NETfor (i=0; i9; i+)

8、II初始化Statein doc .infor (j=0； j9;j+)Stateij = 0;for (i=0; i81; i+) /初始化 StateSortStateSorti0 = i / 9 + 1;StateSorti1 = i % 9 + 1;StateSorti2 = 0;旷doc in银豆网文章内容版权归原作者所有VICHU.NETin doc .in/ Prin t();/ void Load()freopen(input.txt,r,stdin); /输入从 input.txt int x, y, value;while (scanf (%d %d %d, &x, &y,

9、 &value) != EOF)Statex-1y-1 = value;/void Cou nt()算出每一个空元素的所在行和列约束的个数int k;for (i nt i=0; i9; i+)for (i nt j=0; j9; j+)if (Stateij = 0)int nCount = 0;for (k=0; k9; k+) if ( 0 != Stateik) nCoun t+;for (k=0; k9; k+)if (0 != Statekj)nCoun t+;StateSorti*9+j2 = n Cou nt;/ doc in银豆网文章内容版权归原作者所有VICHU.NETin

10、 doc .invoid Sort() int pivotkey3;for (int i=1; i StateSorti-12) pivotkey2 = StateSorti2;pivotkey1 = StateSorti1;pivotkey0 = StateSorti0;for (int j=i-1; (pivotkey2StateSortj2) & (j=0); -j) doc in银豆网文章内容版权归原作者所有VICHU.NETin doc .inStateSortj+12StateSortj2;StateSortj+11StateSortj1;StateSortj+10StateSor

11、tj0;StateSortj+12pivotkey2;StateSortj+11pivotkey1;StateSortj+10pivotkey0;/Prin t();旷doG in银豆网文章内容版权归原作者所有VICHU.NETin doc .in/检查每一个小区内只能出现一次bool ChechZ on e(i nt x, int y, int i)int xZo ne = 3 * (x / 3); /找到每个小区的位置int yZone = 3 * (y / 3);int j = 0;int k = 0;bool flag = true;for (j=xZ on e; jfor (k=yZ

12、 one; kif (x != j | y != k) & Statejk = i)flag = false;goto A1; doc in银豆网文章内容版权归原作者所有VICHU.NETin doc .in旷doG in银豆网文章内容版权归原作者所有VICHU.NETA1:retur n flag;/检查是否符合条件bool ChechAssig n(i nt x, int y, int i)bool flag = true;for (int k=0; k9; k+)if (k != y & i = Statexk)in doc .in旷doG in银豆网文章内容版权归原作者所有VICHU.

13、NETflag = false;if (k != x & i = Stateky)flag = false;if (!ChechZone(x, y, i)flag = false;retur n flag;/int DCou nt ()int g_Count = 0;for (i nt i=0; i= DCou nt() return 1;int x, y;x = StateSortdepth0 - 1;y = StateSortdepth1 - 1;/检查x y有没有被赋值 if (0 != Statexy) return Search (depth + 1);else /尝试赋值in do

14、c .in旷doG in银豆网文章内容版权归原作者所有VICHU.NETfor (i nt i=1; i=9; i+)Statexy = i;/检查是否违反约束条件if (ChechAssig n(x, y, i)if (Search(depth + 1)return 1;Statexy = 0;return 0;/void OutputState()for (i nt i=0; i9; i+)for (i nt j=0; j9; j+)cout Stateij if (0 = (j+1) % 3)cout if (0 = (i + 1) % 3)cout en dl;in doc .incout en dl;cout en dl;/int mai n ()cout = 初始化= endl en dl;In itState();/输入函数Load();OutputState();/计算每个元素所在行列已有的数字个数非空元素为0Cou nt();/Prin t();/cout vv+v/排序Sort();/Prin t();cout The Depth