中文介紹參考: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]
沒有留言:
張貼留言