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

[guguai]

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

https://github.com/qjwgg/sudoku

[Valyrian]

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

[lingo]

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

[lingo]

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

[Killian]

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

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

[guguai]

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

[procen424]

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

[guguai]

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

[guguai]

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

[lingo]

@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]

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

[XadillaX]

一个 DFS 就好了。

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

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

[cfans1993]

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

找一局完整的作模版

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

挖空

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

[guguai]

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

[lingo]

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

[madao]

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

[madao]

@cfans1993 :-)

[guguai]

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

[guguai]

@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]

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

[madao]

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