偶然看到《谈谈 Sudoku (数独)》[1]的博文,心血来潮把文章的算法实现了一番。有关Sudoku的具体介绍可参考维基百科。
具体解法有:回溯、精确匹配。回溯解法《谈谈 Sudoku (数独)》有比较详细的阐述,所以本文只记录一下精确覆盖的解法。
精确覆盖[2]
- 1.精确覆盖
给定集合X、S、T。S是X的子集的集合,T是S的子集,如果X中每个元素都只被T中的一个元素包含,那么T就是X的精确覆盖
- 2.精确命中(exact hitting)
给定集合X、S、Y。S是X的子集的集合,Y是X的子集,如果Y中每个元素都只被S中的一个元素包含,那么Y就是S的精确命中
- 3.表示方法
列表、矩阵
- 4.实现
Knuth's Algorithm X[3],解决精确覆盖的深度优先、递归、不确定算法。
大概思想与技巧[4]:利用矩阵的表示方法,同时把行列表示成双向环列表(Dancing Link),在删除列表中的元素时,只更新前后(上下)的相关指针值。
数度到矩阵的转换
Algorithm X使用了矩阵的表示方法,因此在需要把数度表示成矩阵的形式。具体转换如下:假设一个给定的9 * 9数度中,有N个空格需要求解,矩阵行数R=N * 9,列数C=4 * N,该矩阵用M表示。其中:
a.M[i][j]=1, 0<=j<N,表示第j个空格考虑行、列、块以后可以取数字i%9 + 1
b.M[i][j]=1, N<=j<2N,表示第j个空格只考虑行的情况下可以取数字i%9 + 1
c.M[i][j]=1, 2N<=j<3N,表示第j个空格只考虑列的情况下可以取数字i%9 + 1
d.M[i][j]=1, 3N<=j<4N,表示第j个空格只考虑块的情况下可以取数字i%9 + 1
1.
http://blog.csdn.net/Solstice/article/details/2096209
2.
http://en.wikipedia.org/wiki/Exact_cover
3.
http://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
4.
http://lanl.arxiv.org/PS_cache/cs/pdf/0011/0011047v1.pdf
分享到:
相关推荐
2. 具有“下一步”提示,和步骤追踪“回退”功能 3. 能够保存布局和求解进度 4. 可电脑求解“唯一解”和“所有解” 注意:本软件按照难度分为5级,其中除“最高”级外,其他4级的“电脑布局”都是唯一解。 注意:...
Sudoku数独游戏
Sudoku数独程序编程.pdf
Java SuDoKu数独游戏,一种运用纸、笔进行演算的逻辑游戏。用Java写出的j2me版本的数独,运行于基于Java的手机客户端中。
“数独”(Su Doku)是你和方格之间意志的较量,你不需要大部头词典的帮助,也无需去书店查阅参考书籍,你所需要的东西已经全部在你的大脑中了。在这个精彩旅程中,只有你和“数独”。 这款小游戏或称之为...
写的一个数独游戏,自我感觉算法还可以,就放上来了
是一个用vc++实现的数独游戏,可以锻炼你的智力哦!
本游戏界面简洁,功能完善,堪称数独游戏的完美版本: 1. 按照5级难度自动布局或手工布局,并具有计时功能 2. 具有“下一步”提示,和步骤追踪“回退”功能 3. 能够保存布局和求解进度 4. 可电脑求解“唯一解”和...
数独,九宫格种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字,推理出所有剩余空格的数字,并满足每一行、每一列、每一个粗线宫内的数字均含1-9,不重复。
数独sudoku:整个矩阵由为9*9的矩阵,矩阵中又分成9个3*3的小矩阵,在每个方格中填入1-9 的数字,必须符合列中无重复数字,行中无重复数字,小矩阵中无重复数字 本游戏介绍: 1、游戏模式 a、练习模式,无计时,...
这是一篇关于数独游戏算法的文章,希望对喜爱数独游戏的编程朋友有所帮助。英文版 This is an essay of The Mathematics of Sudoku. Hoping this paper is useful for game programmer.
数独问题算法,针对任意数独问题的一般算法
Matrix Sudoku Solver 解独矩阵是一款计算机模拟人工思路求解数独的程序。它能利用大部分的人工解法完成对简单、中等、困难、专家以及骨灰级的数独求解。玩家可以将需要求解的数独输入矩阵后,按照提示或结合逻辑...
该程序是9*9数独的解决工具,可以根据用户的输入,然后一键补充完整,从而解决数独问题。
用Prolog 解数独, constraint satisfaction problem的方法
数独验证器
javascript sudoku 数独智力游戏生成代码,喜欢的朋友可以参考下。
本代码包含单解数独和多解数独两种解法,注释清晰详细,算法独特,时间和空间复杂度低,对于初学者大有裨益。(另,本题多解数独输出解的总个数,单解数独输出第一个解,代码若直接使用是多解数独的代码,若取消注释...