由棋局走到數獨 - 幻方欣賞二

由幻方走到棋局

國際象棋的棋盤便是一個 8X8  的方陣,這地又會產生不少數學的問題出來,其中與幻方相關的可算是馬步幻方 (Knight's Move Magic Square 或 Knight Square 或 Magic Knight's Tour)。騎士 (Knight) 是國際象棋中一種棋子,走法是沿 2X3 方陣走對角,步如中國象棋的馬。而馬步幻方則是指幻方中各數字也沿馬步而下,奇不奇哉?

 

1 48 31 50 33 16 63 18
30 51 46 3 62 19 14 35
47 2 49 32 15 34 17 64
52 29 4 45 20 61 36 13
5 44 25 56 9 40 21 60
28 53 8 41 24 57 12 37
43 6 55 26 39 10 59 22
54 27 42 7 58 23 38 11
50 11 24 63 14 37 26 35
23 62 51 12 25 34 15 38
10 49 64 21 40 13 36 27
61 22 9 52 33 28 39 16
48 7 60 1 20 41 54 29
59 4 45 8 53 32 17 42
6 47 2 57 44 19 30 55
3 58 5 46 31 56 43 18

左邊的馬步幻方是瑞士數學家歐拉 (Leonhard Euler 1707-1783) 找到的,它的幻和是 260。 我們看到 1 和 64 的位置未成馬步,但再細看,若把方陣卷曲,左右相接,那 1 和 64 又真的成了馬步,形成一個循環。但我得補充一點,這首尾數是否要馬步相接,不是馬步幻方的必要要求。

右邊的馬步幻方改進了這一點,1 和 64 也首尾數馬步相接,便形成一個封閉的馬步徑 (Knight's Tour)。但這兩個幻方的對角線的和跟直、橫各行的和不相同。此等幻方,我們稱為半幻方 (Semimagic Square)。

 

184 217 170 75 188 219 172 77 228 37 86 21 230 39 88 25
169 74 185 218 171 76 189 220 85 20 229 38 87 24 231 40
216 183 68 167 222 187 78 173 36 227 22 83 42 237 26 89
73 168 215 186 67 174 221 190 19 84 35 238 23 90 41 232
182 213 166 69 178 223 176 79 226 33 82 31 236 43 92 27
165 72 179 214 175 66 191 224 81 18 239 34 91 30 233 44
212 181 70 163 210 177 80 161 48 225 32 95 46 235 28 93
71 164 211 180 65 162 209 192 17 96 47 240 29 94 45 234
202 13 126 61 208 15 128 49 160 241 130 97 148 243 132 103
125 60 203 14 127 64 193 16 129 112 145 242 131 102 149 244
12 201 62 123 2 207 50 113 256 159 98 143 246 147 104 133
59 124 11 204 63 114 1 194 111 144 255 146 101 134 245 150
200 9 122 55 206 3 116 51 158 253 142 99 154 247 136 105
121 58 205 10 115 54 195 4 141 110 155 254 135 100 151 248
8 199 56 119 6 197 52 117 252 157 108 139 250 153 106 137
57 120 7 198 53 118 5 196 109 140 251 156 107 138 249 152

再來一個 16 階的馬步幻方,其幻和為 2056。這幻方中,我們同樣找到一個封閉的馬步徑 。這封閉的馬步徑在奇數階的幻方是不可能存在的,為何呢?看看棋盤的黑格、白格相間的情況便明白。還不明白?馬總是由黑格走到白格或由白格走到黑格的。對於偶數階的棋盤,黑白格的數目是相同的,自然有機會找到封閉的馬步徑;但對於奇數階的棋盤則不一樣了,總有一種顏色的格子多了一格,便不可能形成封閉的馬步徑了。

也有數學家找到別的棋子的路徑幻方,如皇步幻方 (King's Move Magic Square 或 King Square 或 Magic King's Tour)、車步幻方 (Rook's Move Magic Square 或 Rook Square 或 Magic Rook's Tour) 等。

 

由數學走到英文

5 22 18
28 15 2
12 8 25
4 9 8
11 7 3
6 5 10

這兩個幻方看來沒甚特別,看似隨意把一些不連續的數字推砌。

但原來這兩個幻方之間有著微妙的關係,看看大家能否看出來。

若然還看不出來,看看這個幻方吧!

Five Twenty-two Eighteen
Twenty-eight Fifteen Two
Twelve Eight Twenty-five

用數字看不清,改用英文寫會否好一點?大家不妨數一數各字的字母數目。對了,右邊幻方的數字正是左邊幻方內的數字的英文名稱的字母數,怪不怪哉。

這樣的一對幻方,我們稱為字母幻方 (Alphamagic Square)。字母幻方亦不只存在英文中,在法文、德文、俄文:任何由字母組成的文字中也可找到的。但由於文字的字母通常不多,故字母幻方的階數也不會太大。

 

由數獨走到幻方

很多人介紹數獨 (Sudoku) 時,都以幻方作引子,把數獨說成幻方的進化版。其實兩者有很大的分別,幻方要求方陣中每個數字均不同,但數獨則不是。

但原來構造幻方也可利用數獨的。但我們先不談數獨先,借它的「祖先」拉丁方 (Latin Square) 先作個引子。如我們想建構一個 n 階的幻方,可以找來兩個正交 (Orthogonal) 的拉丁方。所謂拉丁方便是在 n*n 的方陣內填上 1 至 n ,好使同一橫或直行中每一格的數值不重覆。單看這一點,拉丁方和數獨是相同的。而正交的拉丁方,則是指兩個幻方中的各對應格中的數字組成的兩元素序偶 (Order Pair) 全不重覆,如:

1 2 3
2 3 1
3 1 2
+
1 2 3
3 1 2
2 3 1
=
1,1 2,2 3,3
2,3 3,1 1,2
3,2 1,3 2,1

上例中,我們看見首兩個三階拉丁方成正交,因為第三個幻方中每一格的數值均不相同,其中如 1,3 和 3,1 視作不同。

 

我們先找來兩個正交拉丁方,把原來格中的 1 至 n 改為 0 至 (n-1) ,再把兩個數字合成一個在 n 進制下的兩位數。由於兩拉丁方為正交,故每一格的數字均不相同,但由於不論第一和第二位,0 至 (n-1) 均出現過只此一次,故每一橫、直行中各格數字之和均相同。再把所有數字轉成十進制再加上 1 ,便成了一個 n 階的幻方。我們亦可以下面公式計算各格數值 (N),以 A、B 分別代表兩個拉丁方中的數值:

N = n(A-1) + (B-1) + 1 =  n(A-1) + B

順帶一言,這裡作的幻方只是半幻方 (Semimagic Square) ,因其對角線不守幻和,若連對角線中各值的和也要相同,我們可得花點時間幹一些行與行的對換了。

其實數獨亦是一個九階的拉丁方,若找來兩個「正交」的數獨,也可作一個九階的幻方。當然找一對「正交」的數獨,比找拉丁方難得多。看看下例吧:

 

2 5 8 1 4 7 3 6 9
1 4 7 3 6 9 2 5 8
3 6 9 2 5 8 1 4 7
8 2 5 7 1 4 9 3 6
7 1 4 9 3 6 8 2 5
9 3 6 8 2 5 7 1 4
5 8 2 4 7 1 6 9 3
4 7 1 6 9 3 5 8 2
6 9 3 5 8 2 4 7 1
+
2 9 4 6 1 8 7 5 3
7 5 3 2 9 4 6 1 8
6 1 8 7 5 3 2 9 4
9 4 2 1 8 6 5 3 7
5 3 7 9 4 2 1 8 6
1 8 6 5 3 7 9 4 2
4 2 9 8 6 1 3 7 5
3 7 5 4 2 9 8 6 1
8 6 1 3 7 5 4 2 9
=
11 45 67 6 28 62 25 50 75
7 32 57 20 54 76 15 37 71
24 46 80 16 41 66 2 36 58
72 13 38 55 8 33 77 21 52
59 3 34 81 22 47 64 17 42
73 26 51 68 12 43 63 4 29
40 65 18 35 60 1 48 79 23
30 61 5 49 74 27 44 69 10
53 78 19 39 70 14 31 56 9

 

這個幻方不單連對角線也確守幻和 369,而且它是一個平方幻方,幻和為 20049。當中九個 3*3 的方陣中的數字的和及平方和亦同守幻和。

幻方背後的一對數獨的構造也有一定技巧,我且不說,看看大家是否看得出來?當然的,起碼大家該知道,若把 A、B 互換,也可得 到另一個具有相同性質的幻方來。

 

說到奇特的幻方,何止上述數種?還有一些與素數 (Prime Number) 相關的幻方,則留待另文《連續素幻方》和《再談素幻方》介紹了。

 

參考文獻及網址

Pickover, C. A. The Zen of Magic Squares, Circles, and Stars. New Jersey : Princeton University Press , 2002

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