魔方吧·中文魔方俱乐部

标题: 關於數獨 [打印本页]

作者: 骰迷 时间: 2009-2-20 17:39:22 标题: 關於數獨

大家都玩過、聽過數獨了吧。就是九各九宮格連在一起，填上一至九，令每個小九宮格、每一行、每一列裡的數字都不重複。
做題的時候，題目會提供N個數字，令答案唯一。
好了，問題來了：
N最大值為何？（即隨機位置、安排）
N最少值為何？（即固定位置、安排）

作者: 录 时间: 2009-2-20 17:55:27

最大可以80..

作者: 录 时间: 2009-2-20 18:00:45

還有..就算有77個答案也未必唯一..

作者: 录 时间: 2009-2-20 18:04:21

x2345678x
2          8
3          7
4          6
5          5
6          4
7          3
8          2
x8765432x
好像這樣

[ 本帖最后由录于 2009-2-20 18:09 编辑 ]

作者: 骰迷 时间: 2009-2-20 18:11:44

可能是我的表達有點不清晰。
N是在任意狀態中最少提示的數量，求的是這"最少提示的數量"的最大值。

[ 本帖最后由骰迷于 2009-2-20 18:14 编辑 ]

作者: Xwam 时间: 2009-2-20 18:16:44

我的书里写的题目最多一级36个，最少五级19个
一般22个数的就比较难了

作者: Xwam 时间: 2009-2-20 18:18:18

有一本《竞技数独》，LZ可以看一下

作者: 魔鱼儿 时间: 2009-2-20 18:53:04

经过设计的数独只有唯一的解

作者: tonylmd 时间: 2009-2-20 19:16:04

让我联想到花样版块《2345阶终极打乱》那篇把数独问题放在魔方上不知道会不会有新的研究价值？
http://bbs.mf8-china.com/viewthr ... &extra=page%3D1

作者: aben306 时间: 2009-2-20 19:48:06

不太了解,不懂.

作者: juventus66 时间: 2009-2-20 20:44:34

等高手解答了

作者: 骰迷 时间: 2009-2-21 13:49:07

自己頂一下，順便講講自己對數獨所有狀態數的意見。
先來一個基本態：
123456789
456789123
789123456
234567891
567891234
891234567
345678912
678912345
912345678
我是用什麼方法做出來的，大家都看出來了吧。
現在問題來了：
創造新數獨的方法為
兩橫互換（例：456789123跟789123456調換），不允許跨九宮格換（789123456跟234567891）
兩直行互換
三個九宮格跟三個九宮格互換
是否能確定用以上三個運動方式就能產生出任何數獨？（條件為左上角必定是一）

作者: 骰迷 时间: 2009-2-21 15:02:40

我假設以這三個方法就能造出所有的數獨（一字在左上角）。
那麼數獨的種狀態數可是：2*6*6*2*6*6*2*2*9=186624個？
請高手LULIJIE來編個程驗證一下。
不知此數與本題的解答可有關係。

作者: Vicki 时间: 2009-2-21 15:06:54

LS的讨论的好复杂~我只玩过PSP的~

作者: lulijie 时间: 2009-2-22 13:10:57

我来换了思路来思考。
楼主的一个答案已经出来了，就如楼主所举例的。
第一行是 123456789
现在我让这九个数字随机排列，得到 a1a2a3a4a5a6a7a8a9 总共有9的阶乘=362880种。
现在把楼主的答案中所有的数按照以下方法进行变换：
1→a1，2→a2，3→a3，4→a4，5→a5，6→a6，7→a7，8→a8，9→a9
这样得到的序列必定满足楼组所要求的条件，所以所求的数独的总状态数不会少于362880。

作者: lulijie 时间: 2009-2-22 13:22:57

假设第一行已经排好了，顺序为：a1a2a3a4a5a6a7a8a9
那么满足第一行为a1a2a3a4a5a6a7a8a9的答案有多少种呢，假设为N种，那么
所求的数独的总状态数=N*362880 种。

作者: lulijie 时间: 2009-2-22 13:28:33

按照楼主的构造方法，若第一行固定，那么有 2*6*6*2=144种构造方法.
所以N至少为144，所以总状态数>=144*362880=52254720。

作者: 骰迷 时间: 2009-2-22 14:51:33

我開始想時也是這樣想的，但後來我覺得a9是不必要了。既然前面八個數字定了，後面也確定了。
也可延伸為：若有64個數字定了（8*8=64，可以想像為8*8的正方靠在左上方），其他數字也定了。

作者: lulijie 时间: 2009-2-22 15:29:21

a1a2a3a4a5a6a7a8a9 总状态数为9的阶乘=362880种。
a9在前面8个数确定时，确实已被确定了。
从计算公式可以看出 9*8*7*6*5*4*3*2 最后确定a9时已经100%被确定，所以已经没有乘以系数。

第一行总共有362880种状态，根据对称性，每一种状态都至少确定144种数独答案，所以，总共答案至少有362880*144种。

作者: lulijie 时间: 2009-2-22 17:00:27

第一行为123456789的答案经电脑计算，已算出的有5500种，还在计算：
前10种如下：
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；2；9；7；8；
6；4；2；9；7；8；5；3；1；
9；7；8；5；3；1；6；4；2；
------------------------
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；2；9；7；8；
6；4；8；9；7；1；5；3；2；
9；7；2；5；3；8；6；4；1；
------------------------
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；2；9；7；8；
6；7；2；9；3；8；5；4；1；
9；4；8；5；7；1；6；3；2；
------------------------
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；2；9；7；8；
6；7；8；9；3；1；5；4；2；
9；4；2；5；7；8；6；3；1；
------------------------
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；2；9；7；8；
9；4；2；5；7；8；6；3；1；
6；7；8；9；3；1；5；4；2；
------------------------
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；2；9；7；8；
9；4；8；5；7；1；6；3；2；
6；7；2；9；3；8；5；4；1；
------------------------
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；2；9；7；8；
9；7；2；5；3；8；6；4；1；
6；4；8；9；7；1；5；3；2；
------------------------
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；2；9；7；8；
9；7；8；5；3；1；6；4；2；
6；4；2；9；7；8；5；3；1；
------------------------
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；8；9；7；2；
6；4；2；9；7；1；5；3；8；
9；7；8；5；3；2；6；4；1；
------------------------
1；2；3；4；5；6；7；8；9；
4；5；6；7；8；9；1；2；3；
7；8；9；1；2；3；4；5；6；
2；1；4；3；6；5；8；9；7；
3；6；5；8；9；7；2；1；4；
8；9；7；2；1；4；3；6；5；
5；3；1；6；4；8；9；7；2；
6；4；8；9；7；2；5；3；1；
9；7；2；5；3；1；6；4；8；
------------------------
从第一个和第二个答案比较可知，前65个数完全相同，所以随机65个数确定不了唯一答案。

作者: lulijie 时间: 2009-2-22 20:32:27

第一行为123456789的答案经电脑计算，已算出的有210000种
这21万个答案前面4行全部相同，第5行第一个数计算到5，（电脑是按照从小到大的顺序计算的。）

123456789
456789123
789123456
214365897
5

所以所有满足条件的状态至少有362880*210000种。
其实比这远远还要大。

前100个数独答案.rar (835 Bytes, 下载次数: 3)

附件: [前100个数独答案] 前100个数独答案.rar (2009-2-22 20:32:27, 835 Bytes) / 下载次数 3
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=Mzk1NTd8ODc2ZjAyYWJ8MTcxODUzNDE2MnwwfDA%3D

作者: 骰迷 时间: 2009-2-22 22:30:31

那麼66可會是第一題的答案？
這麼多？！！？二十一萬？！太誇了吧，怪不得這遊戲能天天在不同的報刊刊登，登之不竭了

[ 本帖最后由骰迷于 2009-2-22 22:33 编辑 ]

作者: 骰迷 时间: 2009-2-22 22:36:12

我知道為什麼遠遠比144大了。就像擰一個魔方，限定頂面不動，狀態數不過16個。可是這等不等於所有頂面完好的狀態數？明顯就不是嘛。

作者: lulijie 时间: 2009-2-23 23:24:27

昨天的电脑算法比较慢，算了一夜，只算到第998200个答案，（从小到大的顺序）。
今晚改进了算法，已经算到第2158200个答案：如下
123  456  789
456  789  123
789  123  456
214  367  895
697  518  234
538  942  671
341  875  962
972  634  518
865  291  347

作者: 骰迷 时间: 2009-2-24 18:07:09

關於第一題的答案，我又想了想，是不需66個數字那麼多的。因為算法的關係，是從上到下一行一行的算，讓人忽略了，其實只要左邊的八個數字確定了，右邊的一整行也是不需要的。
另外，辛苦了樓上的電腦，算了一整夜啊！

作者: lulijie 时间: 2009-2-24 22:28:34

是的，一般出题的话，不会把一行9个数都出，但是如果题目要求数字位置是随机的话，就不能规定不许这样。
最新结果：已经计算到第35828200个答案，如下
123456789
456789123
789123456
214937568
837265914
695814237
371642895
968571342
542398671
才第四行有变化，2、3行还没变过。
估计总的答案是个天文数字。

作者: 骰迷 时间: 2009-2-25 18:31:02

我兩題的意思其實是：要求題目給出的數字中　沒有多餘的數字　，並答案惟一時，總數的最大、最小值。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)