数独.docx

数独游戏求解程序（附源代码）2007-08-10 16:00:21| 分类： 我的程序 阅读5777 评论27 字号：大中小 订阅 数独游戏规则是一种源自18世纪末瑞士的数学智力拼图游戏。拼图是九宫格（即3格宽3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。 数独的玩法逻辑简单，数字排列方式千变万化。不少教育者认为数独是锻炼脑筋的好方法。计算机算法简介本文所讨论的算法是一种通用算法，虽然不能说是最快的算法，但却可以求解所有的数独游戏。算法准备：1、一个可能性：表示某个格子可能填写的数字。2、可能性数目：表示某个格子可能性的数量。为0表示已经确定。3、区域标志：表示某个格子所在区域（小九宫）的id，所有区域标志都是预定义的。4、确定数量：表示所有数字已经确定的格子的数量，为81时则表示已经找到解。5、整个九宫格用三个矩阵表示：可能性矩阵，数目矩阵，区域标志矩阵算法的基本思想：步骤1、将所有未确定的格子的可能性定义为0xffff（即所有数字都可能），可能数目为9。步骤2、寻找所有确定的格子a（可能数目为0），在所有与a同行、同列和同区域的未确定的格子的可能性中减去与a相同的可能性。例如：a确定为9，则与a同行、同列和同区域（区域标志相同）的未确定的格子的可能性与0xfeff按位与（除去可能性9），并将其可能性数目减少。在除去可能性的过程中如果发现某个格子b的可能性数目由1减小为0，说明b和a只能取相同的数字，这可能是题目本身无解引起，也肯能是由于步骤3中搜索方向不对引起的，可认为此方向的搜索无解，退出这一方向的搜索。定义这个检查为唯一性检查。步骤3、寻找所有未确定格子中可能性数目最少的格子m，如果m的可能性数目为1，则确定m：将m的可能性数目定义为0，并把确定数量加1，如果此时确定数量达到81，则报告找到解，否则，在所有与m同行、同列和同区域的未确定的格子的可能性中减去与m相同的可能性，并进行唯一性检查。然后重复步骤3。如果m的可能性大于1，则把m假设为所有m的可能性，分多个方向进行搜索，在每一个搜索方向重复步骤3（这个可以用递归来实现）。算法性能本算法可以在50毫秒以内求解任意有解的数独游戏。程序运行画面 程序下载见数独程序开源算法核心代码由于篇幅限制，不能将所有代码贴出来，只贴一些核心的代码，通过研究这些代码已经可以实现本程序。您也可以参照数独程序开源中的程序。/ 优化int cnummatrix:optimize()int x, y;int i;bool changed = true;while(changed)changed = false;for(x = 0; x m_isize; x+)for(y = 0; y m_isize; y+)if(numtrans(m_i16mmatrixxy) = 0)return -1;if(m_cmpossiblexy = 1)m_cmpossiblexy = 0;for(i = 0; i 0)this-removepossible(x, i, m_i16mmatrixxy);if(m_cmpossiblexi = 0)return -1;/ 减少行可能性if(m_cmpossibleiy 0)this-removepossible(i, y, m_i16mmatrixxy);if(m_cmpossibleiy = 0)return -1;/ 减少区域可能性if(!removeregionpossible(m_cmregionxy, m_i16mmatrixxy)return -1;m_iassured+;changed = true;return 0; / 数字翻译int cnummatrix:numtrans(_int16 mask)mask &= (0xffff = -1 & mask 0 & m_isize = nm_max_size & init()for(y = 0; y m_isize; y+)for(x = 0; x setval(x, y, nm_make_mask(tmp);fscanf(fp, %c, &stmp0);elsefclose(fp);return false;fclose(fp);return this-checkpossibility();return false; / 导出到文件bool cnummatrix:writefile(lpctstr filename)file * fp = fopen(filename, w);if(fp)int x, y;int tmp;fprintf(fp, %d %d, %d , m_isize, m_ivregion0, m_ivregion1, m_iassured);for(y = 0; y m_isize; y+)for(x = 0; x = 0)fprintf(fp, %x , tmp);elsefprintf(fp, ? );tmp = numtrans(m_i16mmatrixxy);if(tmp = 0)fprintf(fp, %x , tmp);elsefprintf(fp, ? );fclose(fp);return true;return false; / 减少区域可能性bool cnummatrix:removeregionpossible(char region, _int16 mask)int x, y;for(x = 0; x m_isize; x+)for(y = 0; y 0)removepossible(x, y, mask);if(m_cmpossiblexy = 0)return false;return true; / 可能性检查bool cnummatrix:checkpossibility()int x, y;int i;m_iassured = 0;bool zero = false;for(x = 0; x m_isize; x+)for(y = 0; y m_isize; y+)if(m_cmpossiblexy = 0)m_iassured+;elsem_cmpossiblexy = m_isize;m_i16mmatrixxy = -1;if(m_iassured)for(x = 0; x m_isize; x+)for(y = 0; y m_isize; y+)if(m_cmpossiblexy = 0)for(i = 0; i 0)this-removepossible(x, i, m_i16mmatrixxy);if(m_cmpossiblexi = 0)return false;/ 减少行可能性if(m_cmpossibleiy 0)this-removepossible(i, y, m_i16mmatrixxy);if(m_cmpossibleiy = 0)return false;/ 减少区域可能性if(!removeregionpossible(m_cmregionxy, m_i16mmatrixxy)return false;return true; / 查找解bool cnummatrix:findsolution()static int si = 0;if(optimize() 0)return false;if(m_iassured = m_isize * m_isize)return true;cnummatrix tmp;/ 查找最小可能性的格子int x, y;int mx = -1, my = -1;char min = m_isize + 1;for(x = 0; x m_isize; x+)for(y = 0; y m_isize; y+)if(m_cmpossiblexy != 0 & m_cmpossiblexy min)mx = x;my = y;min = m_cmpossiblexy;/ 取得可能性_int16 possiblenm_max_size;if(mx = -1)return false;int sum = getpossibleval(mx, my, possible);/ 遍历可能性int i;for(i = 0; i sum; i+)memcpy(&tmp, this, sizeof(cnummatrix);tmp.setval(mx, my, possiblei);if(tmp.checkpossibility() & tmp.findsolution()memcpy(this, &tmp, sizeof(cnummatrix);return true; return false;/我这里还有一个很好的数独解法,不过.这个我本人不怎么看得懂/#include stdafx.h#include #include #include #include /棋盘数组,ij=k表示第i个行，第j列存放数字kint mvararrbox99;/预置数组/2006-10-12 改为使用bit做标志/mvararrpreboxi的第j位上为1，表示i,j上有数unsigned short int mvararrprebox9;/*小方块标志数组,mvarsmallboxi第j位表示第i个小方块中，数字j出现的个数2006-10-12 改为使用bit做标志*/unsigned short int mvarsmallbox9;/*列标志数组,mvararrcolumnsi第j位表示第i列中，数字j出现的个数2006-10-12 改为使用bit做标志*/unsigned short int mvararrcolumns9;/*行标志数组,mvararrrowsij表示第i行中，数字j+1出现的个数2006-10-12 改为使用bit做标志*/unsigned short int mvararrrows9;/函数声明void init();void usage(char *programname);bool readdat(file *input);void gosearch();void output();bool fillin(int i, int j, int k);void remove(int i,int j);/新加的位操作函数bool setbit(unsigned short int intarr, int i,int j ,bool k);bool getbit(unsigned short int intvalue, int j );/初始化void init()int i,j;for (i=0;i9;i+)for (j=0;j9;j+)mvararrboxij=0;mvararrcolumnsi=0;mvararrrowsi=0;mvarsmallboxi=0;void usage(char *programname)fprintf(stderr,%s.exe write by xmxoxo nusage:n,programname);/* modify here to add your usage message when the program is* called without arguments */printf(%s.exe inputfilen,programname); /* returns the index of the first argument that is not an option; i.e.does not start with a dash or a slash*/int handleoptions(int argc,char *argv)int i,firstnonoption=0;for (i=1; i1)strcpy(input_file_name,argv1);/打开文件 r表示读，b表示二进制方式input_file=fopen(input_file_name,rb);if (input_file=null)printf(input file name? );scanf(%s,input_file_name);/打开文件 r表示读，b表示二进制方式input_file=fopen(input_file_name,rb);if (input_file=null)printf(fatal error opening files.n);return 1;/初始化init();/读数据bool blnret=readdat(input_file);fclose(input_file);/判断初始数据是否正确;if (!blnret)printf(read dat error!n);output();return 0;/输出初始状态printf(初始状态：n);output();/搜索gosearch();return 0;/读取初始数据bool readdat(file *input)unsigned int character;bool blnret=0;int i=0;int j=0;while (true)/读入一个字节的数character=getc(input)-48; /0;/如果是数字if (character=0 & character=9)/放到棋盘数组中/非0,则在预置数组中做标志;if (character!=0)if (!fillin(i,j,character)return 0;setbit(mvararrprebox,i,j+1,1);if (+j=9)if (+i=9)break;j=0;if (feof(input) break;return 1;/搜索结果void gosearch()int total=0;int i=0;int j=0;int k=0;bool bfind=false;while (true)if (i0 | j8 | j8)/是，表示找到一个结果，printf(第%d个结果：n,+total);/输出结果；output ();printf(n);/要找下一个结果吗？/if (allresult)if (true) /要，继续返回，如何返回？i=8;j=9;/回到上一个非预置位置do if (-j0)j=8;i-;if (i8) break;while (getbit(mvararrpreboxi,j+1);/printf(前进-%d%d=%dn,i,j,mvararrboxij);/否/找一个可填的数并写入bfind=false;/读出当前位置值为基数for (k=mvararrboxij+1;k8)break;while ( getbit(mvararrpreboxi,j+1);/printf(前进-%d%d=%dn,i,j,mvararrboxij);else/没有能填入的数字/清空当前位置的值remove(i,j);/输出调试信息/printf(清空,%d%dn,i,j);/回到上一个非预置位置do if (-j0)j=8;i-;if (i0)break;while (getbit(mvararrpreboxi,j+1);/printf(返回-%d%d=%dn,i,j,mvararrboxij);/*位操作函数将数组中第i个数的第j位置k(k=0,1)设置成功返回true;否则返回false;*/bool setbit(unsigned short int intarr, int i,int j ,bool k)unsigned short int inttmp;/构造运算符;/inttmp=(k)?(1(j-1):0xffff-(1(j-1);if (k)inttmp=1(j-1);/设置为1intarri |= inttmp;elseinttmp=0xffff-(1(j-1);/设置为0intarri &= inttmp;return 1;/*判断intvalue的第j位状态返回0或者1;*/bool getbit(unsigned short int intvalue, int j )/unsigned int是4字节，32bit;/unsigned short int是2字节，16bit; /左移，去掉左边位；intvalue=15;return (intvalue)?true:false;/*将k填入ij位置如果检查出已重复，则不填入值，并返回false，否则填入并返回true;*/bool fillin(int i, int j, int k)/int intpre=0;if (!getbit(mvararrrowsi,k)& !getbit(mvararrcolumnsj,k)& !getbit(mvarsmallbox(i/3)+(j/3)*3,k) )/移除原来的值remove(i,j);/填写到当前空