Sudokus

最近網路上似乎很流行一種遊戲：Sudokus。



中文介紹參考：21世紀數字拼圖益智遊戲Sudoku

這不就是魔術方陣(magic square)嗎？

剛好最近代數學上到這哩，就來談一下好了。(蔡炎盛老師該不會是因為最近流行這個才上魔術方陣吧？)

所謂的魔術方陣，是從拉丁方陣(Latin Square)而來。拉丁方陣是指 N x N 的方陣中，用 N 個元素去填，每一行或者每一列的元素都不可以重複。EX.
1-2-3
2-3-1
3-1-2
就算一個拉丁方陣。

而更進一步，限制使用 N x N 個元素填值且每一行每一列的和都相同，就稱為魔術方陣。

魔術方陣怎麼找？可以用程式來算，參考Gea-Suan Lin’s BLOG：Sudokus

不過只是這樣嗎？當然不是。

其實魔術方陣和代數學有關。先回頭看看拉丁方陣，這樣的形式是不是很像是 group 的 operation table？

Definition:

若兩個 N x N 的拉丁方陣 L, K 重疊合成為 G，則 G 的元素可表示為 g_ij = (l_ij, k_ij) for 0<=i<=(N-1), 0<=j<=(N-1)。若 G 之任兩元素不相等，則稱 L, K 為正交。

Lemma:

|GF(p,m)| = n 的群，最多可以組成 n-1 個兩兩正交的 n x n 的拉丁方陣集合。p 是質數，m 是任意正整數，n=p^m。

因此，以 3x3 為例，只有兩個兩兩正交的拉丁方陣：
A-B-C
B-C-A = L
C-A-B

A-B-C
C-A-B = K
B-C-A

G = L x K, let g_ij = n x l_ij + k_ij, G' = g_ij + 1
接下來只要決定，A,B,C對應什麼值({A,B,C} --> {0,1,2})就可以創出一個魔術方陣了。(L and K 的 A,B,C 可以不用同一組 map。)

至於對於玩 Sudoku 遊戲有沒有幫助？我沒有抓這個遊戲來玩，所以也不清楚。

我之所以打這篇，是覺得真的很神奇，這些數學家的大腦是怎麼想的啊？感覺一點關係都沒有的東西，用這麼曲折的方式連在一起。真是太神奇了。


Tag: [Math], [CourseNote]