大家觉得这个数独生成方法（算法）怎么样？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 3546 天前的主题，其中的信息可能已经有所发展或是发生改变。

生成步骤：
1. 生成数独终盘
a. 遍历整个数独，随机（从其候选值中进行随机）获取每个单元格的值
b. 若能走到最后，则表示生成数独终盘成功，否则重新进行步骤 1，直至成功
2. 在终盘中进行挖洞，生成具有唯一解的数独难题
a. 一次性挖取 n 个洞（n 根据难度进行设定），表现即为随机将数独中的 n 个单元格的值置为 0
b. 挖取完毕后，进行求解，来判定挖取后的得到的数独难题的解是否唯一。
c. 若能求解，则其解唯一，否则重新进行步骤 a、b，直至能够求解成功，生成数独难题

https://github.com/qjwgg/sudoku

成数

生成

随机

43 条回复 • 2015-03-14 13:16:55 +08:00

takato

2015-03-11 10:38:20 +08:00

数独目前应该只能通过穷举（即搜索）来完成
你的伪码应该就是求解步骤。但是遍历量非常大

目前最有效优化方法应该是DLX（Dancing Links）
参考：
http://zh.wikipedia.org/wiki/舞蹈链

takato

2015-03-11 10:39:18 +08:00

抱歉，不好意思看错了，我以为是求解。

生成的话其实也可以倒过来用.....

jmc891205

2015-03-11 10:41:37 +08:00

从终盘上挖洞之后得到的题目肯定有解的吧？

stupidcat

2015-03-11 10:59:30 +08:00

> a. 遍历整个数独

这句看不懂，能否解释一下？

21grams

2015-03-11 11:07:14 +08:00

思路貌似没什么问题，但我总觉得应该有更好的办法。

guguai

2015-03-11 12:29:52 +08:00

@stupidcat 就是遍历数独列表。此句意思就是遍历数独，为数独中每一个格子进行赋值

guguai

2015-03-11 12:31:14 +08:00

@jmc891205 嗯，是有解，但不保证是有唯一解。所以是在挖洞后还需要进行唯一解确认。

saber000

2015-03-11 12:54:59 +08:00

我感觉问题会出在随机获取每个单元格的值这一步

c742435

2015-03-11 13:11:54 +08:00

@takato 总共会有多少种数独？
感觉从编码复杂度上说原型继承非常适合这类穷举，但效率应该就不行了。

takato

2015-03-11 13:15:34 +08:00

@c742435 数独是NP-Complete，所以除了穷举没有任何数学方法，DLX起到的是一个剪枝作用。

takato

2015-03-11 13:16:28 +08:00

@c742435 即在你遍历的时候，你能够非常快的回到上一个状态

Tink

2015-03-11 14:04:08 +08:00

这遍历的量太多了吧

guguai

2015-03-11 14:08:24 +08:00

@saber000 这一步确实会出问题，只是有时候会出问题。在代码中我是出问题了就重来，程序运行给我的感觉是大部分是不会有问题的。

guguai

2015-03-11 14:10:13 +08:00

@Tink (⊙v⊙)嗯~~

guguai

2015-03-11 14:46:12 +08:00

@takato 在github中也有一个求解的方法实现。

saber000

2015-03-11 15:39:11 +08:00

@guguai 我是觉得一开始用随机填值是没有问题的,但是随着填上的格子的增加,随机填的方法效率越来越低,到后期应该要改变填值策略,遍历+回溯都比随机填要好.

a569171010

2015-03-11 17:21:06 +08:00

数独游戏必须只能有一个解。
我的思路：生成终盘，然后扣洞，随机抠一个然后1-9进行尝试，能生成唯一终盘接着扣第二个洞，能生成两个结果的回退，再随机扣，洞越多运算量越大，所以基本上只能扣到一定数量要不然性能是问题。

个人感觉生成终盘有2种：1：随机法 2：先从1开始排直到81，有顺序排好，然后想办法打乱。

lingo

2015-03-11 17:34:45 +08:00

我这几天正在写数独。LZ用2.7写的。。我用3.4写的。。。
目前进度是只能解题还不能生成题目。。
主要还是卡在效率上。暴力遍历解题效率太差了。一般的题目1秒内没问题。。但是我这有一道题，已知数字只有16个。遍历需要5分钟。。
我打算的出题思路是生成终盘。然后随机挖洞。挖一个洞解一次，保证只有唯一解。可是每次都要遍历出所有借的话按照上面那个题目的时间来看没办法。。
目前纠结中。

loddit

2015-03-11 17:50:57 +08:00

我想知道编数独书的人怎么怎么出的题呢？
ps. 我两年前写了个多人数独 sudoku.meteor.com 但是题库很少，正好可以用楼主的服务来出题的了。

gleport

2015-03-11 17:52:24 +08:00

@lingo 我以前写过一个 DLX 数独求解器, 求解速度很快, 一般的题目 0.01s 内没问题.
地址: https://github.com/hmgle/sudoku_solver

Valyrian

2015-03-11 18:00:13 +08:00 via iPhone

@lingo 16个书那个解是唯一解吗？我记得看过一篇论文提到保证唯一解至少需要17个数

lingo

2015-03-11 18:03:53 +08:00

@loddit 自动出题只能让题目的数量上面不愁。。但是题目的质量良莠不齐。因为其他都是随机的，所以难度只能依靠空格的数量来控制，这点比手工出题差了不少。

lingo

2015-03-11 18:06:52 +08:00

@Valyrian 好吧我数错了。。正好17个。

Killian

2015-03-11 18:15:29 +08:00

1 在生成的时候 index i不从1加到81，而是做一个permutation
2 index从不同的位置赋值，比如先赋值4个角

不确定以上改变对最终有什么影响~~

guguai

2015-03-11 19:18:55 +08:00

@lingo 你那个16数字的数独能贴出来吗，我看看我写的数独求解方法能不能解出来。

procen424

2015-03-11 21:48:29 +08:00 via Android

为什么要从头开始生成呢。。。
1.搜集已有的终盘数据，做为模板存下来。或者自己枚举几个。
2.随机生成新的映射关系，替换模板里的数字
3.挖洞。如果发现存在多组解，是没有关系的，因为游戏结束的条件是解合法，而不是解与原盘面一致。

guguai

2015-03-11 21:55:34 +08:00

@procen424 我感觉，多解的情况是不合理的。比如，我举一个极端的例子，数独只有一个格子有值，它肯定是多解的，但显然这样没有意义~~

guguai

2015-03-11 22:00:43 +08:00

@saber000 格子中的随机值是从这个格子的候选数中进行随机的。就是说这个随机值对于这个格子来说，肯定是正确的。只是有时候会不满足数独的定义，所以需要重新来过。也就是我贴出的1b步骤

lingo

2015-03-11 22:30:05 +08:00

@guguai
0, 8, 2, 0, 9, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 5,
0, 1, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 3, 2, 0,
7, 0, 0, 5, 0, 6, 0, 0, 0,
0, 0, 0, 7, 0, 0, 0, 0, 0,
0, 3, 0, 9, 0, 0, 0, 0, 0,
0, 0, 0, 0, 2, 0, 0, 8, 0,
5, 0, 0, 0, 0, 0, 0, 0, 6
好像是这个。之前数错了。17位。

lingo

2015-03-11 22:31:58 +08:00

@guguai 解肯定是能解出来的。解出来后还请告知解了多长时间。

XadillaX

2015-03-11 22:53:44 +08:00

一个 DFS 就好了。

这是我以前年轻不懂事还在用 code.google.com 的时候写的：

https://code.google.com/p/xadillax-personal/source/browse/trunk/C%23/Sudoku/Sudoku/Sudoku.cs#250

cfans1993

2015-03-12 07:08:04 +08:00 via Android

学线性带数的学生汪来溜溜

找一局完整的作模版

选一个正九宫作行列变换：将穿过这九个格子的三列相互调换，行调换也类似。下一个正九宫、重复

挖空

用户填完检查、值得考虑的唯一性问题不知道能不能用矩阵的determination作判断

guguai

2015-03-12 09:39:43 +08:00

@lingo (⊙﹏⊙)b，我写的那个数独求解方法，解不出你的这个题，看来还需要修改修改了~

lingo

2015-03-12 11:09:45 +08:00

@guguai 你确定是解不出来不是你给的时间不够？我第一次解也以为解不出来。。后来第二解的时候我去打了一把游戏。。。游戏打玩切出来看。。解出来了。。后来我profile.run测试了一下时间。。用了320秒。。

madao

2015-03-13 11:29:39 +08:00

先读一个必然合理的终盘，然后随机两两互换，这是最简单的方案。

madao

2015-03-13 11:31:04 +08:00

@cfans1993 :-)

guguai

2015-03-13 14:24:02 +08:00

@madao 这也是一个方法，玩玩还是可以的。但是这种方法随机性就比较差，有经验的人（或者多玩几道题）估计就能看出来有一定的规律了（或者似曾相识）~

guguai

2015-03-13 15:23:23 +08:00

@lingo 刚刚发现，你这个数独的解不唯一呀，看看这两个：
3, 8, 2, 1, 9, 5, 7, 6, 4,
4, 6, 7, 2, 8, 3, 9, 1, 5,
9, 1, 5, 4, 6, 7, 8, 3, 2,
6, 5, 1, 8, 4, 9, 3, 2, 7,
7, 2, 9, 5, 3, 6, 1, 4, 8,
8, 4, 3, 7, 1, 2, 6, 5, 9,
2, 3, 6, 9, 5, 8, 4, 7, 1,
1, 7, 9, 6, 2, 4, 5, 8, 3,
5, 4, 8, 3, 7, 1, 2, 9, 6

4, 8, 2, 1, 9, 5, 7, 6, 3,
3, 6, 7, 2, 8, 4, 9, 1, 5,
9, 1, 5, 3, 6, 7, 8, 4, 2,
6, 5, 1, 8, 4, 9, 3, 2, 7,
7, 2, 3, 5, 1, 6, 4, 9, 8,
8, 4, 9, 7, 3, 2, 6, 5, 1,
2, 3, 6, 9, 5, 8, 1, 7, 4,
1, 7, 4, 6, 2, 3, 5, 8, 9,
5, 9, 8, 4, 7, 1, 2, 3, 6

madao

2015-03-13 17:38:46 +08:00

@guguai 随机数量上去之后，相似值会很低，然后加上XY轴交换，那就是完全随机，这样的方法效率极高。

madao

2015-03-13 17:39:29 +08:00

@guguai 原理上任意一个终盘通过移位都能转换成一个固定的终盘。

lingo

2015-03-14 10:07:08 +08:00

@guguai 你自己看看你的第一个解有没问题。。。第三列。。吓死我了。。

lingo

2015-03-14 10:07:55 +08:00

还有第二列

guguai

2015-03-14 13:16:55 +08:00

@lingo (⊙o⊙)…抱歉，丢脸了~~~看来我那数独求解方法是有大问题了