- 浏览: 169499 次
- 性别:
- 来自: 广州
博客专栏
-
TCP/IP详解卷一>阅读...
浏览量:12550
文章分类
最新评论
-
master11:
你好,博主看完你的解释,好厉害啊!!佩服。如果想运行看一下效果 ...
数独人工解法的一些技巧及其python实现 -
evasiu:
chenxun1012033254 写道lz这么辛苦我也是醉了 ...
数独人工解法的一些技巧及其python实现 -
chenxun1012033254:
lz这么辛苦我也是醉了作为一名oier我说有一个算法叫做dan ...
数独人工解法的一些技巧及其python实现 -
xuyfiei:
lz很厉害,现在该是毕业了吧
恨毕业--读研一年总结 -
nphoenix:
呵呵 肯踏實的學東西已經很不錯了。畢業了工作之後,你就會發現個 ...
恨毕业--读研一年总结
随着数独解题算法DLX的完成,产生一个数独迷题的任务就顺理成章地完成了。当然,基本的思想还是先生成终盘,然后对填好的数独题进行挖洞,每挖一个洞,就要考虑一下挖去这个洞会不会导致迷题将有多个解。假如会,这个洞就是不能挖的。事实上当一个洞被证实挖去之后会导致多解后,这个洞就注定不能被挖了。也就是说,这个算法的复杂度应该是81*O(f(n)),其中f(n)是用于解一个数独的时间复杂度。
《编程之美》里面提供了一种生成终盘的方法,即在数独中间的块(B5)上随机填入1~9,然后利用这个块行列变换到旁边的块(B4跟B6、B2跟B8)上,同样的做法将在B4、B6上填充B1跟B7,B3跟B9,从而得到一个合法的数独终盘。这种方法将可以产生 9! 种数独终盘。前面的文章我们已经讨论过了,总共存在 6.67*10^21 种数独终盘,相比之下 9! 未免也太少了吧?于是我决定另谋思路。
现在我们已经得到了解数独的方法,我的思路是,对角线上的三个块(B1,B4,B7)是可以随便填而不会造成不合法行为的,把这三个块随机填完后,再利用DLX进行求解,就可以得到一个终盘了。虽然我们知道对于同一个初始局面(B1、B4、B7被随机填好),DLX是可以得到很多个解的,但是由于算法本身的确定性,因此产生终盘的顺序也是固定的,也就是说,这种做法下,我们只能得到(9!)^3,大概是 10^14 种数独终盘。我因此产生了一个想法,把算法的结果弄得有点不是那么确定。我们知道,当我们确定性地选了一列拥有最少元素的列后,算法的思路是深搜该列下的每一行,当通过该行最终得到了一个解后,就返回结果了。为了使算法具有不确定性,我决定在选择行的时候,带上一点随机性质:随机选一个行来进行深搜。这样,我们理论上就能得到所有可能的数独了。
接下来便是挖洞。前面我们大概提到了,当我们尝试挖一个洞而该洞使数独迷题拥有多解时,该洞就不能被挖了,无论我们后面挖了哪些格子。因此,每个格子都只最多会被尝试挖一次。这样的话我们可以首先一个[0,81)的随机序列,然后按照该序列的顺序对终盘进行挖洞,直到所有的格子都被挖过,或者未填的空格已经满足要求后算法才停止。如何判断该挖去该洞后会否使数独迷题拥有多个解呢?那就是,选中某个格子后,假设该格中原先的值为i,那么我们就分别用[1,9]中除了i以外的数替换i,再对数独进行求解,如果能得到解,说明挖去该洞会使数独存在不止一个解。算法虽是这么描述,在真正实现的时候还是可以做一定的优化的。不过我通过实验发现,一般最多只能挖去59个洞,也就是说有得到的数独迷题最少有22个提示,看资料说目前为止数独迷题有唯一解的最少的提示可以达到17个,大概在选格子的顺序上是需要一点处理的。
具体实现的时候,我使用了上篇文章最后提到的那个只有30几行的dlx实现版本,原因是这样进行随机选行方便了很多,呵呵。我在代码里面做了大量的注释。不过为了保证copy时不会出现错误,我都用的英语注释。
好了,接下来我要去研究一下pygame了,先把基础界面做出来,再考虑数独的难度、人工解法及提示。come on ~
《编程之美》里面提供了一种生成终盘的方法,即在数独中间的块(B5)上随机填入1~9,然后利用这个块行列变换到旁边的块(B4跟B6、B2跟B8)上,同样的做法将在B4、B6上填充B1跟B7,B3跟B9,从而得到一个合法的数独终盘。这种方法将可以产生 9! 种数独终盘。前面的文章我们已经讨论过了,总共存在 6.67*10^21 种数独终盘,相比之下 9! 未免也太少了吧?于是我决定另谋思路。
现在我们已经得到了解数独的方法,我的思路是,对角线上的三个块(B1,B4,B7)是可以随便填而不会造成不合法行为的,把这三个块随机填完后,再利用DLX进行求解,就可以得到一个终盘了。虽然我们知道对于同一个初始局面(B1、B4、B7被随机填好),DLX是可以得到很多个解的,但是由于算法本身的确定性,因此产生终盘的顺序也是固定的,也就是说,这种做法下,我们只能得到(9!)^3,大概是 10^14 种数独终盘。我因此产生了一个想法,把算法的结果弄得有点不是那么确定。我们知道,当我们确定性地选了一列拥有最少元素的列后,算法的思路是深搜该列下的每一行,当通过该行最终得到了一个解后,就返回结果了。为了使算法具有不确定性,我决定在选择行的时候,带上一点随机性质:随机选一个行来进行深搜。这样,我们理论上就能得到所有可能的数独了。
接下来便是挖洞。前面我们大概提到了,当我们尝试挖一个洞而该洞使数独迷题拥有多解时,该洞就不能被挖了,无论我们后面挖了哪些格子。因此,每个格子都只最多会被尝试挖一次。这样的话我们可以首先一个[0,81)的随机序列,然后按照该序列的顺序对终盘进行挖洞,直到所有的格子都被挖过,或者未填的空格已经满足要求后算法才停止。如何判断该挖去该洞后会否使数独迷题拥有多个解呢?那就是,选中某个格子后,假设该格中原先的值为i,那么我们就分别用[1,9]中除了i以外的数替换i,再对数独进行求解,如果能得到解,说明挖去该洞会使数独存在不止一个解。算法虽是这么描述,在真正实现的时候还是可以做一定的优化的。不过我通过实验发现,一般最多只能挖去59个洞,也就是说有得到的数独迷题最少有22个提示,看资料说目前为止数独迷题有唯一解的最少的提示可以达到17个,大概在选格子的顺序上是需要一点处理的。
具体实现的时候,我使用了上篇文章最后提到的那个只有30几行的dlx实现版本,原因是这样进行随机选行方便了很多,呵呵。我在代码里面做了大量的注释。不过为了保证copy时不会出现错误,我都用的英语注释。
from itertools import product from random import shuffle import timeit N_Cell = 3 N = 9 GRIDS = 81 def exact_cover( X, Y ): X = {j:set() for j in X} for i, row in Y.items(): for j in row: X[j].add(i) return X, Y def select( X, Y, r ): cols = [] for j in Y[r]: for i in X[j]: for k in Y[i]: if k!=j: X[k].remove(i) cols.append(X.pop(j)) return cols def deselect( X, Y, r, cols ): for j in reversed(Y[r]): X[j]=cols.pop() for i in X[j]: for k in Y[i]: if k!=j: X[k].add(i) def solve( X, Y, solution=[], isRandom=False ): if not X: return list(solution) else: c = min(X, key=lambda c:len(X[c])) rows = list(X[c]) #shuffling the rows results in picking a row in random if isRandom: shuffle(rows) for r in rows: solution.append(r) cols = select(X, Y, r) if solve(X, Y, solution): #we don't use yield anymore, #instead, when a solution found, return it return solution deselect( X, Y, r, cols ) solution.pop() #they are contributed mostly by: http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html #helper function #given index of row, colunm and the ans in the corresponding cell #return colunms that should be one in this context def get_ones( r, c, n ): b = (r//N_Cell)*N_Cell + (c//N_Cell) ones = [("rc", (r, c)), ("rn", (r, n)), ("cn", (c, n)), ("bn", (b, n))] return ones def puzzle_generator(): #identifier for columns are static, we have our index from 0 #when("rc",(r,c)) has a one, it means sudoku grid (r,c) has been filled #when("rn",(r,n)) has a one, it means sudoku line r already has a number n #when("cn",(c,n)) has a one, it means sudoku column c already has a number n #when("bn",(b,n)) has a one, it means sudoku block b already has a number n X_init=([("rc", rc) for rc in product(range(N), range(N))]+ [("rn", rn) for rn in product(range(N), range(1, N+1))]+ [("cn", cn) for cn in product(range(N), range(1, N+1))]+ [("bn", bn) for bn in product(range(N), range(1, N+1))]) #Y and Y_final records lines (r,c,n) has which columns as one #where Y is for solving the randomly generated puzzle #while Y_final is for recording the final answer, #if there is a Y_final[(r,c,n)], that means grid[r][c]has been filled with n Y = dict() Y_final = dict() #puzzle we are going to generate, initially all 0 puzzle = [ ([0]*N) for i in range(N) ] for i in range(N_Cell): init = range(1, N+1) #generate a random sequence from 1~9 and fill them one by one to the blocks #lines are added to Y and Y_final in correspondance, prepare for diggin cells shuffle(init) for j in range(N_Cell): for k in range(N_Cell): r = i*N_Cell+j c = i*N_Cell+k n = init[j*N_Cell+k] puzzle[r][c]=n Y[(r,c,n)]=list(get_ones(r,c,n)) Y_final[(r,c,n)] = list(get_ones(r,c,n)) #other unfilled cells are 0, there are more than one possibilities for them #which means we have Y[(r,c,i)](i=1~9) for j in range(N_Cell): for k in range(2*N_Cell): r = (6+i*N_Cell+j)%N c = (i*N_Cell+k)%N for n in range( 1, N+1 ): Y[(r,c,n)]=list(get_ones(r, c, n)) #convert it to a exact_cover problem and solve it #the final answers are added to Y_final X, Y = exact_cover(X_init, Y) solution = solve(X, Y, isRandom=True) for (r, c, n) in solution: puzzle[r][c]=n Y_final[(r,c,n)]=list(get_ones(r, c, n)) #begin digging, we have no investigation on how many cells should be digged for a specific difficulty #so here we made it 60 in temporary, that's, we have 21 hints #but running result shows that we can hardly have 60 cells digged successfully, most of the time 50+ empty = 60 done = 0 tries = 0 #dig the cells in a random order seq = range(GRIDS) shuffle(seq) while done<empty and tries<GRIDS: #main idea: try each cell(r,c,n) where cell(r,c) is filled with n #pop (r,c,n) from Y_final, replace it with other (r,c,i)(i!=n) r, c = divmod(seq[tries], N) tries += 1 n = puzzle[r][c] for i in range(1, N+1): Y_final[(r,c,i)]=get_ones(r,c,i) Y_final.pop((r,c,n)) #this is a new exact_cover problem #we are replace the initial n in cell(r,c) with other i #to see if there is an answer for it X,Y_final=exact_cover(X_init, Y_final) #if not, that means we can't get an answer from it, #we can safely delete the cell, that is, puzzle[r][c]=0 if( not solve(X,Y_final) ): puzzle[r][c]=0 done += 1 #if yes, that means this cell can be filled with other number and #still we get a legal sudoku, the cell can't be deleted #so Y_final[(r,c,i)] should be pop else: for i in range(1,n)+range(n+1, N+1): Y_final.pop((r,c,i)) #finally, the initially deleted line, (r,c,n) should be push in Y_final[(r,c,n)]=get_ones(r,c,n) print 'empty:', done return puzzle if __name__ == '__main__': puzzle = puzzle_generator() for row in range(len(puzzle)): print puzzle[row]
好了,接下来我要去研究一下pygame了,先把基础界面做出来,再考虑数独的难度、人工解法及提示。come on ~
发表评论
-
我对KM算法的理解
2012-12-26 15:47 25848一般对KM算法的描述, ... -
一个小题目(单词统计)
2012-08-14 23:12 1316今天休息的时候看到一个关于单词统计的小题目: 统计一段由字符 ... -
数独人工解法的一些技巧及其python实现
2012-06-13 16:31 6602这段日子实现了十几种 ... -
Eva'Sudoku-0.1新鲜出炉啦~~
2012-05-27 21:06 1327呵呵,经过将近一个星期的对pygame的了解与熟悉,我终于磕磕 ... -
解数独——dancing link X
2012-05-21 22:59 7961折腾了一个星期,发现 ... -
总共有多少个数独?
2012-05-12 15:31 12741憋屈地看了一个星期的 ... -
编程之美续
2012-04-06 15:37 1115看完编程之美后看很多题,都会发现原来只是里面一些题目的变种(也 ... -
编程之美
2012-04-02 16:54 1411前段日子又看了编程之美,后来闲着无聊学python去了,想着书 ... -
数据结构——2-3树
2012-02-10 14:25 7143年前实现了一个2-3树, ... -
数据结构 -- 二叉树(BST, AVLTree, RBTree, SplayTree)
2012-01-17 21:31 2761在《基于树的索引结构介绍》(http://philoscien ... -
编程珠玑--关于查找(二分法、自组织链、哈希)
2011-12-31 19:36 2103查找是我们现实生活中 ... -
编程珠玑 -- 关于堆
2011-12-28 15:31 1132堆是这样一种数据结构,它首先是一棵二叉树,而且还是一棵完全二叉 ... -
编程珠玑 -- 关于排序
2011-12-27 20:12 976《编程珠玑》主要提到 ... -
Heritrix总结及消重算法初探
2011-06-02 12:38 2616好久没有更新博客了。最后一次更新居然已经是一个月以前的事了。忍 ... -
图论--旅行商问题
2011-05-04 14:57 1462五一果然基本献给了数据压缩(除了两个晚上用于打球),看了小波的 ... -
图论--寻找欧拉回路
2011-04-27 21:05 1782首先介绍一下fleury算法。 大概描述是这样子的: (1 ... -
图论--中国邮递员问题
2011-04-27 20:25 13969中国邮递员问题就比较 ... -
图论--关键路径
2011-04-27 19:37 1834最近忙着做作业。主要是《代数与图论》的一些算法的实现,五一估计 ... -
C语言中的文件操作
2011-04-16 11:34 781常常觉得,我对很多东西都是要求会用就好,不求甚解。比如说每次一 ...
相关推荐
最小数独拼图生成器考虑一个已解决的数独谜题。 然后,删除一个数字。 由此产生的谜题是否仍然只有一个独特的解决方案? 是的当然。 如果你一遍又一遍地这样做,直到你有一个仍然有唯一解决方案的谜题,但任何进一步...
解决和创建不同级别(邪恶、困难、中等、简单等)的数独谜题。 给出了两个求解器: 人们试图找到尽可能多的解决方案。 另一个给出了它找到的一个解决方案。 有关详细信息,请参阅 readme.txt。 玩得开心。
它适用于解决复杂的、全局性的优化问题,包括数独谜题的求解。遗传算法的核心思想是模拟自然选择、遗传、突变和交叉等生物进化机制来逐步优化解决方案。 在Java中实现遗传算法解决数独,首先需要定义数独的表示方式...
通过对1000个典型数独谜题进行独立评估,得到了与www.websudoku.com上由数百万用户实际解决时间产生的难度分布类似的结果。 ###### 3.3.3 运行时间分析 hsolve算法的运行时间取决于数独谜题的复杂程度。对于简单至...
在生成唯一解的数独时,算法需要确保每个数独谜题有且只有一个解。这通常通过控制预填数字的数量和分布来实现。预填数字越多,谜题难度越低;反之,预填数字越少,难度越高。同时,为了保证唯一解,算法在填充数字时...
数独求解工具和代码(VC6)是一个基于Windows界面的应用程序,专为解决数独谜题而设计。这个程序采用C++编程语言,并利用Microsoft Visual C++ 6.0开发环境进行构建。数独是一种逻辑游戏,目标是填满9×9的网格,...
我们都知道,数独游戏的魅力在于挑战和解决谜题的过程。《数独计算器第二版》的题目生成功能满足了用户的不同需求。软件能生成从简单到复杂的多种难度级别的数独题目,且每个题目都保证了有唯一的正确解。如此一来,...
这个项目可能是通过以上技术实现的,提供了用户友好的界面来生成、解决和验证数独谜题。对于初学者,这是一个很好的实践项目,可以帮助他们巩固Java基础知识,理解GUI编程,以及学习如何用算法解决问题。对于有经验...
Keith Corlett 的开源数独解释器解释了任何数独谜题,并生成了人类谜题。 这是一个 Java (Swing) GUI,基于 Nicolas Juillerat 的 DIUF Sudoku Explainer(为了速度而重写),所有提示都来自 Bernhard Hobiger 的 ...
通常情况下,一个数独谜题会提供一定数量的“线索”(已填好的数字)作为解题的起点。数独最小线索数问题就是询问数独谜题至少需要多少个线索才能保证有一个唯一的解。 在McGuire的论文中,作者们提出了一种新的...
通过这样的教学设计,学生在解决数独谜题的过程中,不仅可以提高数学技能,还能锻炼思维敏捷性,培养耐心和专注力,同时享受到数学的乐趣,从而对数学产生更深层次的兴趣和热爱。这门课程不仅是对传统数学教育的补充...
一旦数独谜题生成了多个解决方案,该算法就会撤消最后一次删除,并将其保留为谜题。 当前,用户只有两个选项:寻求提示或获取完整的解决方案。 如果有兴趣,则需要进一步改进: 4x4、16x16数独 用户界面可在空白...
"sudoku:基于 euristics 的数独求解器"是一个使用C++编写的程序,专门用于解决数独谜题。在这个项目中,"euristics"指的是用于优化解题过程的启发式策略,这些策略通常比简单的暴力搜索更高效。 在C++编程语言中,...
交叉操作模拟生物的杂交过程,通过交换基因来产生新的基因组合。 5. 变异(Mutation):对生成的个体进行变异,即以一定概率随机改变某些基因的值。变异操作模拟生物的突变现象,增加种群的多样性,防止早熟收敛。 6...
通过这个程序,用户可以在空格中输入已知数字,软件会自动计算并填充剩余的数字,完成数独谜题。 MFC是微软为Windows应用程序提供的一套类库,它是基于C++的,主要用于简化Windows API的使用。这个项目使用MFC,...
产生generate :在给定的难度级别上生成数独谜题,并返回预期的答案。 难度级别:“易”,“中”,“难”和“ v_hard ”,其中“易”难题的线索最多。 “生成”功能给出的预期答案有望与回溯解决方案产生的答案有所...
AutoSudoku是一款基于JavaScript的数独求解器,利用了前向检查(Forward Checking)和 Dancing Links (Dancing Links, 简称DLO或DLX) 算法来解决数独谜题。这款软件设计精良,用户体验友好,为数独爱好者提供了一个...
通过这个版本,用户不仅能够直接使用这款工具生成数独谜题,还可以在此基础上进一步开发和创新,例如增加图形用户界面、优化算法效率、甚至开发出可以自动生成数独谜题解答的子程序等。这样的开放性无疑为数独爱好者...