数独如何生成

GreenKite

当时想做个软件，里面带个 9*9 的数独的功能，但发现不太好搞。

退而求其次，做了个 4*4 的。

当时我觉得瓶颈主要在如何生成一个有唯一解的数独，做 4*4 的时候，第一个想法是随机数随便生一个，跑一遍看看有没有解，但我比较懒，感觉这样写起来位置要判重、判唯一解比较麻烦（也许不麻烦，反正我没写），最后用的方法是把所有可行的数独都生一遍，发现非常有限，大约几千个吧，然后随机取一个数独，再随机数生位置（经试验最少需要 5 个），然后把这几个位置的数在所有数独里都取出来，看看那个取出来的数独的这几个位置的数字排列是不是唯一的，跑的飞快，当然规模小直接搜索也跑的飞快，谁知道呢。

所以说，如果要生成 9*9 的唯一解数独应该怎么搞？生成所有的数独显然规模过大，目前只能想到随机数生成（生成的过程中位置判重）+DLX 验证，但感觉有点麻烦，复杂度也有些摸不准，不知道会不会太慢。

求助，有没有坛友有研究过这个问题的？一般的数独是怎么生成的？

三滑稽甲苯

可以在 GitHub 上找找看大佬们的代码，比如说这份就是用 Java 生成数独的 https://github.com/ErkanCicek/Su ... BoardGenerator.java

GreenKite

三滑稽甲苯 发表于 2024-2-24 14:37
可以在 GitHub 上找找看大佬们的代码，比如说这份就是用 Java 生成数独的 https://github.com/ErkanCicek/S ...

唔，粗略一看，这份看起来像是先生成一个数独再镂空？
我设想的是可以控制最终剩下来的数字的数量，可能要再叠一层搜索回溯，不知道会不会慢......
有空去试试看。

GreenKite

GreenKite 发表于 2024-2-24 16:04
唔，粗略一看，这份看起来像是先生成一个数独再镂空？
我设想的是可以控制最终剩下来的数字的数量，可能 ...

确实，这样简单一点，之前我是想的复杂了

adamfh

直接镂空是最简单的，但你得测试是否有多个解

有多个解的数独，是不正确的。

数独应该有唯一解。

测定数独是否有唯一解的计算量不算太大。


关于数独的研究很多，我建议先看看怎么玩数独，然后看看怎么做数独。


另外，深入玩数独后，会发现数独是个很无聊的游戏，不过考虑可以简单的数独，做启蒙。

先用链玩数独吧：）

GreenKite

adamfh 发表于 2024-2-24 17:13
直接镂空是最简单的，但你得测试是否有多个解

有多个解的数独，是不正确的。

不，我上面说的不清楚，并不是直接镂空，而是每次镂空一个数试试，并且每次检查目前是否仍有唯一解。

不过事实上，实现的时候，为了保证时间复杂度，我仍然打算使用 DLX 验证而非搜索。

只是，需要研究怎么解数独吗？毕竟计算机的计算量和人脑不一样，我认为没有必要按人脑解数独的方法研究算法，毕竟 17 提示数的数独的世界纪录是 2min？（不知道有没有记错），但显然 DLX 或者 搜索+剪枝 只需 1s。

GreenKite

但是目前（凭空想想）仍然有一些问题，比如我上面我需要控制剩下的数字数量，我不确定当提示数过少时会不会导致程序跑太久，或许在这种情况下我需要考虑别的算法

GreenKite

事实上，判断唯一解在一些极端数据上真的会被卡，计算量会很大的，不过一般的确实暴力搜索也没问题

jyjjf

好多数独游戏都是现成的字典弄的

adamfh

GreenKite 发表于 2024-2-24 17:53
不，我上面说的不清楚，并不是直接镂空，而是每次镂空一个数试试，并且每次检查目前是否仍有唯一解。

...

没没没，我只是建议你玩玩数独而已。
因为研究到后面，感觉这游戏有点无聊。


暴力搜索花不了多少计算量。
当然，最好是提前放一些有唯一解的数独题，不一定要自己生成啥的。