關於數獨

骰迷

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

骰迷

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

lulijie

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

骰迷

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

lulijie

昨天的电脑算法比较慢，算了一夜，只算到第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

骰迷

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

骰迷

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

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

lulijie

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

123456789
456789123
789123456
214365897
5


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

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

2009-2-22 20:32:27 上传

下载次数: 3
前100个数独答案

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

lulijie

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

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