數獨的數學

 

數獨與拉丁方

數獨 (Sudoku) 是近期風行全港的填寫式數學玩意,可動腦筋,在繁忙的都市生活中帶來一丁點新情意。

所謂數獨,是在一給定的 9x9 的方陣 (Matrix) 中的空格上填上 1 至 9 這 9 個數字中其中一個,使每一直行、橫行及九個 3x3 的小方陣中均有 1 至 9 的數字各一。

 

數獨始於 1979年,由一位叫卡因斯 (H. Garns) 的人提出,且刊登於他的一本數學問題集中。後來問題流傳至日本且被發揚光大。其實數獨的問題和拉丁方 (Latin Square) 不無關係。所謂拉丁方,即把 N 個數字填在一 NxN 的方陣中,使每一直行、橫行上均有 N 個不同的數字。當然數獨的要求比九階拉丁方要求更高,我們也可把之視作九階拉丁方的特例。

 

九階拉丁方有多少個?數獨又有多少不同的款式?

首先我們得知在拉丁方中,數字本身並無特別意思,即 1 和 2 並無分別。故任意的行列互換或數字對換也會成為拉丁方,這兩個拉丁方我們只視之為一。在數獨上可有點不同,但原則相若,若可經過行列互換或數字對換而成的新數獨,我們也視之為一。

那麼有多少?九階拉丁方有 377597570964258816 個之多,數獨也有 5472730538 個之多,但若把經過行列互換或數字對換而成的新數獨都計算在內的話,則有 6670903752021072936960 之多。

 

我們填解數獨,所以重的方法不外是看看每一格的可能數值,把答案可能個數較少的先填,再以推測、試錯等方法把沒有可能的答案剔除,重而得解。

 

 

最小數獨問題

有數學家借題發揮,利用數獨找尋更大的數學思考空間。如有人問:我們要給定最少多少個數字才可使數獨的答案是唯一的呢?數學家萊利 (G. Royle) 發現了 30000 個給定 17 個數字的數獨可給出唯一的答案,而 16 個數字的則找不到一個可給出唯一的答案。但這只能使我相信最小數獨問題 (Minimum Sudoku Question) 是答案很有可能是 17 ,但未經證明。而本人亦相信,在某個角度來看,此三萬個給定 17 個數字的數獨應該也是數獨中最「難 」的問題了,故順手牽羊牽來三個給網友自娛。

(答案就在本頁中,網友找找看看吧。)

 

6
9
3
7
8
4
5
1
2
4
8
7
5
1
2
9
3
6
1
2
5
9
6
3
8
7
4
9
3
2
6
5
1
4
8
7
5
6
8
2
4
7
3
9
1
7
4
1
3
9
8
6
2
5
3
1
9
4
7
5
2
6
8
8
5
6
1
2
9
7
4
3
2
7
4
8
3
6
1
5
9
6
2
8
9
4
5
1
7
3
1
5
3
6
7
2
4
8
9
9
4
7
3
1
8
6
5
2
7
6
4
1
5
3
2
9
8
2
8
1
7
9
6
5
3
4
5
3
9
2
8
4
7
6
1
3
7
6
4
2
9
8
1
5
4
1
5
8
3
7
9
2
6
8
9
2
5
6
1
3
4
7
4
1
6
5
2
3
7
9
8
7
5
9
8
4
6
1
2
3
8
3
2
1
7
9
5
4
6
5
9
7
2
6
1
8
3
4
6
4
1
7
3
8
9
5
2
2
8
3
4
9
5
6
1
7
3
7
8
9
5
4
2
6
1
9
2
4
6
1
7
3
8
5
1
6
5
3
8
2
4
7
9

 

數獨可以是一個動腦筋的遊戲,但也可以是數學科的研習課題,這只取決於我們怎樣利用這工具。

 

 

參考文獻及網址:

Bammel, S. E. and Rothstein, J. "The Number of 9x9 Latin Squares." Disc. Math. 11, 93-95, 1975.

Garns, H. "Number Place." Dell Pencil Puzzles & Word Games. No. 16, May p. 6, 1979.

Royle, G. "Minimum Sudoku." http://www.csse.uwa.edu.au/~gordon/sudokumin.php.

Royle, G. "Sudoku Patterns." http://www.csse.uwa.edu.au/~gordon/sudokupat.php.

Weisstein, E. W. "Latin Square." From MathWorld. http://mathworld.wolfram.com/LatinSquare.html.

Weisstein, E. W. "Sudoku." From MathWorld. http://mathworld.wolfram.com/Sudoku.html.