1
takato 2015-03-11 10:38:20 +08:00
数独目前应该只能通过穷举(即搜索)来完成
你的伪码应该就是求解步骤。但是遍历量非常大 目前最有效优化方法应该是DLX(Dancing Links) 参考: http://zh.wikipedia.org/wiki/舞蹈链 |
2
takato 2015-03-11 10:39:18 +08:00
抱歉,不好意思看错了,我以为是求解。
生成的话其实也可以倒过来用..... |
3
jmc891205 2015-03-11 10:41:37 +08:00
从终盘上挖洞之后得到的题目肯定有解的吧?
|
4
stupidcat 2015-03-11 10:59:30 +08:00
> a. 遍历整个数独
这句看不懂,能否解释一下? |
5
21grams 2015-03-11 11:07:14 +08:00
思路貌似没什么问题,但我总觉得应该有更好的办法。
|
8
saber000 2015-03-11 12:54:59 +08:00
我感觉问题会出在随机获取每个单元格的值这一步
|
12
Tink 2015-03-11 14:04:08 +08:00
这遍历的量太多了吧
|
13
guguai OP @saber000 这一步确实会出问题,只是有时候会出问题。在代码中我是出问题了就重来,程序运行给我的感觉是大部分是不会有问题的。
|
16
saber000 2015-03-11 15:39:11 +08:00
@guguai 我是觉得一开始用随机填值是没有问题的,但是随着填上的格子的增加,随机填的方法效率越来越低,到后期应该要改变填值策略,遍历+回溯都比随机填要好.
|
17
a569171010 2015-03-11 17:21:06 +08:00
数独游戏必须只能有一个解。
我的思路:生成终盘,然后扣洞,随机抠一个然后1-9进行尝试,能生成唯一终盘接着扣第二个洞,能生成两个结果的回退,再随机扣,洞越多运算量越大,所以基本上只能扣到一定数量要不然性能是问题。 个人感觉生成终盘有2种:1:随机法 2:先从1开始排直到81,有顺序排好,然后想办法打乱。 |
18
lingo 2015-03-11 17:34:45 +08:00
我这几天正在写数独。LZ用2.7写的。。我用3.4写的。。。
目前进度是只能解题还不能生成题目。。 主要还是卡在效率上。暴力遍历解题效率太差了。一般的题目1秒内没问题。。但是我这有一道题,已知数字只有16个。遍历需要5分钟。。 我打算的出题思路是生成终盘。然后随机挖洞。挖一个洞解一次,保证只有唯一解。可是每次都要遍历出所有借的话按照上面那个题目的时间来看没办法。。 目前纠结中。 |
19
loddit 2015-03-11 17:50:57 +08:00
我想知道编数独书的人怎么怎么出的题呢?
ps. 我两年前写了个多人数独 sudoku.meteor.com 但是题库很少,正好可以用楼主的服务来出题的了。 |
20
gleport 2015-03-11 17:52:24 +08:00
|
22
lingo 2015-03-11 18:03:53 +08:00
@loddit 自动出题只能让题目的数量上面不愁。。但是题目的质量良莠不齐。因为其他都是随机的,所以难度只能依靠空格的数量来控制,这点比手工出题差了不少。
|
24
Killian 2015-03-11 18:15:29 +08:00
1 在生成的时候 index i不从1加到81,而是做一个permutation
2 index从不同的位置赋值,比如先赋值4个角 不确定以上改变对最终有什么影响~~ |
26
procen424 2015-03-11 21:48:29 +08:00 via Android
为什么要从头开始生成呢。。。
1.搜集已有的终盘数据,做为模板存下来。或者自己枚举几个。 2.随机生成新的映射关系,替换模板里的数字 3.挖洞。如果发现存在多组解,是没有关系的,因为游戏结束的条件是解合法,而不是解与原盘面一致。 |
27
guguai OP @procen424 我感觉,多解的情况是不合理的。比如,我举一个极端的例子,数独只有一个格子有值,它肯定是多解的,但显然这样没有意义~~
|
28
guguai OP @saber000 格子中的随机值是从这个格子的候选数中进行随机的。就是说这个随机值对于这个格子来说,肯定是正确的。只是有时候会不满足数独的定义,所以需要重新来过。也就是我贴出的1b步骤
|
29
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位。 |
31
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 |
32
cfans1993 2015-03-12 07:08:04 +08:00 via Android
学线性带数的学生汪来溜溜
找一局完整的作模版 选一个正九宫作行列变换:将穿过这九个格子的三列相互调换,行调换也类似。下一个正九宫、重复 挖空 用户填完检查、值得考虑的唯一性问题不知道能不能用矩阵的determination作判断 |
34
lingo 2015-03-12 11:09:45 +08:00
@guguai 你确定是解不出来不是你给的时间不够?我第一次解也以为解不出来。。后来第二解的时候我去打了一把游戏。。。游戏打玩切出来看。。解出来了。。后来我profile.run测试了一下时间。。用了320秒。。
|
35
madao 2015-03-13 11:29:39 +08:00
先读一个必然合理的终盘,然后随机两两互换,这是最简单的方案。
|
37
guguai OP @madao 这也是一个方法,玩玩还是可以的。但是这种方法随机性就比较差,有经验的人(或者多玩几道题)估计就能看出来有一定的规律了(或者似曾相识)~
|
38
guguai OP @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 |
42
lingo 2015-03-14 10:07:55 +08:00
还有第二列
|