關於數獨

juventus66

等高手解答了

骰迷

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

骰迷

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

Vicki

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

lulijie

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

lulijie

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

lulijie

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

骰迷

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

lulijie

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

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

lulijie

第一行为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个数确定不了唯一答案。