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

[guguai]

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

https://github.com/qjwgg/sudoku

[takato]

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

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

[takato]

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

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

[jmc891205]

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

[stupidcat]

> a. 遍历整个数独

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

[21grams]

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

[guguai]

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

[guguai]

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

[saber000]

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

[c742435]

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

[takato]

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

[takato]

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

[Tink]

这遍历的量太多了吧

[guguai]

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

[guguai]

@Tink (⊙v⊙)嗯~~

[guguai]

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

[saber000]

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

[a569171010]

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

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

[lingo]

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

[loddit]

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

[gleport]

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