数独源程序py.doc

#!/usr/bin/python#coding=utf-8#sudoku#import randomclass sudoku(object): def _init_(self): self.col = 0 self.row = 0 self.num = i for i in range(9) # 初始化数独数据 self.sd = 0 for column in range(9) for row in range(9) def Clear(self ): 清空当前格的数值 self.sdself.rowself.col = 0 def GenSudoku(self): pass def isOK(self, bit ): 是否满足行、列和3X3区域不重复的要求 return ( self.checkRow( bit ) and self.checkCol(bit) and self.checkNine(bit) def checkRow(self, bit): 检查行是否符合要求,行没有重复 if bit in self.sdself.row: return False return True def checkCol(self, bit): 检查列是否符合要求, 列没有重复 for i in range(9): if bit = self.sdiself.col: return False return True def checkNine(self, bit): 检查3X3区域是否符合要求, 区域中没有重复的记录 #获得左上角的坐标 i = self.row / 3 * 3 j = self.col/ 3 * 3 #横向检查 if bit in self.sdij:j+3 or bit in self.sdi+1j:j+3 or bit in self.sdi+2j:j+3 : return False return True def Next(self): 下一填充格 if self.col = 8: #Debug #print row now., self.row self.row = self.row +1 self.col = 0 else: #print col now., self.row, self.col self.col = self.col +1 def Prev(self): 上一填充格 if self.col = 0 : self.row = self.row -1 self.col = 8 else: self.col = self.col -1 #清除当前的数字，方便重新填充 self.Clear() def isEnd(self): 填充完成 return( self.row = 9 ) def genNum(self): 生成随机数字1-9 #初始化数字序列 num = n for n in range(1,10) for i in range(9): #生成随机数字 ranNum = random.choice ( num ) #检查随机数字合法 if( self.isOK( ranNum ) ): #返回数字 return ranNum #如没有满足的数字，返回0 return 0 def ranFix(self): #按照填充格，逐个填充 while 1: #产生随机数字 n = self.genNum() #返回0, 回退到上一个填充格 if n = 0: #回退 self.Prev() continue else: #填充随机数字，并进行到下一个填充格 self.sdself.rowself.col = n self.Next() #填充完成，结束 if self.isEnd(): break #打印 for i in range( 9 ): print self.sdiif _name_ = _main_: shudu = sudoku() shudu.ranFix()我写了一个数独求解程序（看本文最后面），首先在最顶的文本框输入700100400030080070006004001800700600070090020002003007500900200090060040001005008共81个数字，表示一个9*9数独，再按一下init(initialize)按钮，就用这些数字初始化了下面的矩阵，然后再按solve按钮就是可算出结果了。有唯一解就会给出唯一解，如果有多解就填入能唯一确定的数值。当然你可以自己构造一组数据来输入。copy按钮是把矩阵的结果复制到上面的文本框（方便复制）Hint按钮是提示功能，提示当前可以进行的操作帮忙找找有没有什么bug，找到的话高分相赠，谢谢。主要是软件计算方面，有没有本应唯一解的却解不出，多解的当成唯一解，或者无解的出现错解等等。-第三版更新：增加推理过程显示第四版更新：界面友好化第五版更新：增加推理条件，算法加强第六版更新：增加推理条件，算法加强，加强无解判定，推理过程显示有少量修改第七版更新：增加推理条件（三数集法等），界面显示有修改，推理过程内容显示有修改第八版更新：增加推理条件（简单染色法），推理过程内容显示增加英文第九版更新：增加了题目生成功能和题目难度判断功能，本功能还在测试中。第十版更新：算法加强，特别加强了唯一性判定，特别难题目自动加深搜索第11版更新：算法加强，特别增加即时代码编译运行接口第12版更新：算法加强，多解、无解判定速度加快，生成题目速度加快，本版本保证不会误判解的情况。第13版更新：算法加强，修正多解判定时一个会导致计算过慢的问题，增加了五种推理方法，难度计算有修改第14版更新：算法加快，判断解的情况的算法速度再次提高，修正计算难度的Bug第15版更新：主要是Bug修正，较14版和13版稳定第16版更新：求解广度修正，内存泄露问题修正，增加求解时间统计，生成的题目50%以上是难题（以笔算为准）。关于这个新增加的接口，有Solve和Make两个不同程序，通过标准输入和输出交互，Solve程序的main返回值表示解答结果，需要使用MinGW编译器编译运行。使用时只要在本软件里直接输入C+代码，就可以编译链接成一个Shell随时调用，你可以把自己的Solve代码或者Make代码写进去作为本软件的一个扩展功能。详细接口信息见软件内说明(option按钮)。programmingSudoku蛮有趣的游戏，忘了最早是在哪看到的了。反正是有次坐火车，为打法无聊的时间，买了本数独的书，之后就无聊时偶尔玩起。初级的题目蛮简单的，但是后来的真有些让人头晕脑胀。总之，不适合在上班的路上玩。只适合午后坐在角落里，晒着暖暖的阳光或者冷冷的空调杀时间。当然，若是能手捧着咖啡或者有佳人相伴就更好了:D 不过，喜欢玩这种的女生应该不多吧。最初接触时，就在想，完全该写个程序来解，真不知道计算机是让人变聪明还是变傻了。两个月前看编程之美的时候，里边也有讲到数独的生成及其解决的算法，但看过就忘了:)算法这种东西自己不研究基本上记不住。所以一直拖到现在。今天太晚，明天边学Python边写个生成和解决数独的代码贴上来好了。这里写下需求记着，免得到时候忘。 能自动生成一个待求解的数独，最好能按照指定的难度生成。打印到屏幕上或保存到文件里，字符界面即可。 按指定格式，输入一个待求解的数独，能判断是否可解，若可解，给出解法。 同上条，但不用给出解法，只要给出目前空格中“可能”的值即可。比如说，对于某一格，若其所在行或者列已经有数字1，3，5，7那么将给出可能的值2，4，6，8，9，即剔除明显错误的值。设计思路，应该混杂了编程之美中的东西了吧。不过在写完之前我也不打算翻出来求证了，免得失去了自己的东西。回头比较下算法效率。 分为两个程序，一个负责生成数独，叫做sudoku_gen，一个负责解数独sudoku_solve。它们之间用定义好的接口可以联合使用。 对数独的描述，可以用A，B，C，.，H，I来分别表示第一到第九行；用1，2，.，8，9来分别表示第一到第九列。即第二行第二列的各自用B2表示。对于整个数独状态，用二维数组存储即可。 对格子的潜在值分析函数possible_nb，给定数独和格子位置描述，即可以返回可能的值组成的数组。 对于sudoku_gen。1. 思路是先随机生成最中间那个小九宫格的结果。 2. 然后对其上、下、左、右四个小九宫格的每个格子用possible_nb处理，对返回结果随机选取一个值填入。 3. 之后再同样处理角上的四个小九宫格。 4. 此时就能得到完整的一个九宫格，再根据输入的难度参数，随机遮盖掉每个小九宫格的一些格子，这样生成了初始的数独题目。 难度参数还没想好怎么控制，到时候再说。先把每个九宫格里遮盖掉同样个数个格子好了。不过需要考虑的是不能将一行或一列全部遮盖或者全都没遮盖吧。 输出数独题目，在文件result.txt里保存遮盖前的答案。 对于sudoku_solve。1. 首先将所有空的各自排序，按照其所在行、列、小九宫格里已经填有数字的格子的个数，即已经填有数字的格子越多，那么该空格子的优先级越高，排在越前边若优先级相同则采用先后顺序。 2. 用possible_nb处理排序好的空格子，如果只有一个可能值，则填入该格子，并更新其相关行列上的所有其他空格子的可能