数独 精品.docx

数独游戏求解程序（附源代码）20XX-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 umMatrix: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 umMatrix: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 umMatrix: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 umMatrix: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 umMatrix: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 umMatrix:FindSolution()static int si = 0;if(Optimize() 0)return false;if(m_iAssured = m_iSize * m_iSize)return true;umMatrix 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(umMatrix);tmp.SetVal(mx, my, possiblei);if(tmp.CheckPossibility() & tmp.FindSolution()memcpy(this, &tmp, sizeof(umMatrix);return true; return false;/我这里还有一个很好的数独解法,不过.这个我本人不怎么看得懂/#include stdafx.h#include #include #include #include /棋盘数组,ij=k表示第i个行，第j列存放数字kint mvarArrBox99;/预置数组/20XX-10-12 改为使用bit做标志/mvarArrPreBoxi的第j位上为1，表示i,j上有数unsigned short int mvarArrPreBox9;/*小方块标志数组,mvarSmallBoxi第j位表示第i个小方块中，数字j出现的个数20XX-10-12 改为使用bit做标志*/unsigned short int mvarSmallBox9;/*列标志数组,mvarArrColumnsi第j位表示第i列中，数字j出现的个数20XX-10-12 改为使用bit做标志*/unsigned short int mvarArrColumns9;/*行标志数组,mvarArrRowsij表示第i行中，数字j+1出现的个数20XX-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);/填写到当前空格