魔方陣 Magic Square

這個是我們資料結構(Data Structure)的第二次作業,
本文紀錄了奇數雙偶數以及單偶數魔方陣(Magic Square)的做法。

老實說,上課不斷的聯想到太鼓達人的★9曲「魔方陣-サモン・デルタ-」

魔方陣定義

魔方陣定義是這樣的:

  • 每一行(Column)的總和
  • 每一列(Row)的總和
  • 對角線的總和
  • 上面每一個值都相等

這邊採用了直行橫列的說法。

比方說:

618
753
294
115144
12679
810115
133216

接下來我會記錄如何製作魔方陣。

奇數魔方陣

奇數的魔方陣是魔方陣中比較簡單的一種,構造方式相當容易。
正常情況下,給定一個 n 在 O(n2) 時間複雜度內就可以完成。

  • 第一列(Row)中間放「1」
  • 不斷往左上角移動(走出方格從對面出現)、放入下一個數字
  • 如果左上角空間已有數字,則往下放一格

以 3x3 魔方陣為例(n = 3):

第一步:在中間上面放「1」

1

第二步:不斷往左上走。同時累進數字。
(這個 1 從上方跑出方陣、於是 2 應該在下面。)

1
2

我們接下來不斷重複。

1
2
1
3
2

第三步:這個 3 的左上方已經有數字,於是往下放一格。

1
3
24

依照這個步驟繼續完成。

618
753
294

我們最終就得到一個不錯的方陣。

算法

只要考慮跑出方陣、以及碰撞到有值的格子就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
...
//計算下一步的座標
x = (x - 1 < 0)? width : x - 1;
y = (y - 1 < 0)? height : y - 1;

//如果下一步有值
if(!empty(map[x][y]))
{
//先回到上一步
x = tx;
y = ty;

//往下移動一格
y = (y + 1 > height)? 0 : y + 1;
}

//確定位置後,填入數值
map[x][y] = value;

//記錄這一步的座標
tx = x;
ty = y;
...

演示

雙偶數魔方陣

雙偶數指的是 4 的倍數。這類型的魔方陣比奇數更複雜一些。
雙偶數的魔方陣的做法:

  • 按照順序填入
  • 找到主對角線
  • 找到副對角線
  • 把不在對角線上的值依序取下
  • 把取下的值從後面反過來填上

重點在於,何謂主、副對角線呢?
這邊的解釋是,任何可以切割成方格的樣子。

n = 4
1234
5678
9101112
13141516
n = 8
12345678
910111213141516
1718192021222324
2526272829303132
3334353637383940
4142434445464748
4950515253545556
5758596061626364

從上圖就可以看出來,藍色背景的是我所認知的「主對角線」、而紅色背景是「副對角線」。

  • 當 n = 4 時,沒有副對角線。
  • 當 n ≧ 8 時,有副對角線。

算法

最麻煩的是、你如何抓對角線呢?
讓我們來仔細觀察看看:

(0, 0)(3, 0)(4, 0)
(1, 1)(2, 1)
(1, 2)(2, 2)
(0, 3)(3, 3)(4, 3)
(0, 4)(3, 4)(4, 4)

不曉得有沒有發現呢? 他縱向、橫向的規律是一致的。
然後他對角線上的值有這樣的特性:

  • 位置 = (x, y)
  • 如果 x % 4 = 0 或 3 且 y % 4 = 0 或 3(上方紅色)
  • 如果 x % 4 = 1 或 2 且 y % 4 = 1 或 2(上方藍色)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
...
//弄個陣列
array = []

//遍歷位置
for(x is 0 to width)
for(y is 0 to height)
{
//屬於非對角線的話,推入陣列
if(belong(x, y))
array.push((x, y));
}

//翻轉陣列
array.reverse();

//最後填回
for(x is 0 to width)
for(y is 0 to height)
{
//屬於非對角線的話,從陣列中回填
if(belong(x, y))
(x, y) = array.pop();
}
...

這樣就可以把雙偶數魔方陣完成。

演示

單偶數魔方陣

這是所有方陣中最複雜的。但其也有跡可循。
然而我們可以觀察到,它的大小:n = 4k+2
舉例來說:

k = 1、n = 4+2 = 6
k = 2、n = 8+2 = 10

注意:當 k = 0 時,則 n = 2 的 2x2 魔方陣並不存在。

除了奇數、4的倍數外、剩下的剛好都是 4k+2 的形式。
這種方陣的樣貌大致上呈現:

n = 6 ( k = 1 )
3516261924
3327212325
3192222720
82833171015
30534121416
43629131811
n = 10 ( k = 2 )
929918156774265865
9880714167355326466
468895225456387072
8587192136062447153
869325296168505259
17247683904249513340
2358289914830573941
79811320972931634547
10129486783537694628
111810077843643752734

這邊來敘述這種方陣的構成:

  • 先構造一個 (n / 2) 的魔方陣,作為子方陣
  • 拼合 4 個子方陣(規則下面會說明)
  • 透過 k = (n - 2) / 4 求出 k
  • 搬動方陣內的元素

我們以 n = 6 為例子。
首先,我們得構造一個 3x3 的魔方陣:

618
753
294

接著我們要拚合子方陣。先看下圖:

AB
CD

總共會把子方陣複製 4 份貼在 6x6 的方陣中。
不過還得加上一個常數:m x (n / 2)2

  • A 區塊m = 0、所以方陣中元素 + 0
  • B 區塊 m = 2、所以方陣中元素 + 2 x 32 = 18
  • C 區塊 m = 3、所以方陣中元素 + 3x 32 = 27
  • D 區塊 m = 1、所以方陣中元素 + 1x 32 = 9

將其累進拚合後:

618241926
753252321
294202722
332835151017
343230161412
293631111813

這樣就拚合了 4 個子方陣成為一個大的 6x6 方陣。
不過還沒有完成。我們得搬動一些元素才行。

接著,透過 k = (n - 2) / 4 求出 k。n = 6、代表 k = 1 。
然後把矩陣分成上下兩塊:

618241926
753252321
294202722
332835151017
343230161412
293631111813

搬動元素的規則為:

  • 上面區塊的左上角 kxk 方陣跟下方換。
  • 上面區塊的左下角 kxk 方陣跟下方換。
  • 上面區塊的中間列(Row)從 k位置向右 k 格跟下方換
  • 上面矩陣的 (n/2) + floor(n/4) (也就是右半邊的中間)處向右 (k - 1) 格跟下方換

實際標記看看:

上面區塊的左上角 kxk 方陣跟下方換(k = 1)

618241926
753252321
294202722
332835151017
343230161412
293631111813
3318241926
753252321
294202722
62835151017
343230161412
293631111813

上面區塊的左下角 kxk 方陣跟下方換(k = 1)

3318241926
753252321
294202722
62835151017
343230161412
293631111813
3318241926
753252321
2994202722
62835151017
343230161412
23631111813

上面區塊的中間列(Row)從 k 位置(綠框)向右 k 格(藍框)跟下方換(k = 1)
(※ 不含綠框)

3318241926
753252321
2994202722
62835151017
343230161412
23631111813
3318241926
7323252321
2994202722
62835151017
34530161412
23631111813

上面矩陣的 (n/2)+floor(n/4) 處向右 (k - 1) 格跟下方換,
這邊理解一下,雖然看起來很複雜,但 (n/2) 是子方陣的大小、(n/2)/2 = 子方陣大小的一半。
從綠框處(含)、往右 0 格(藍框、因為是 0 而無法顯示)

3318241926
7323252321
2994202722
62835151017
34530161412
23631111813
3318241926
7323252321
2994202722
62835151017
34530161412
23631111813

這樣最後得到的,就是完好的魔方陣了。

3318241926
7323252321
2994202722
62835151017
34530161412
23631111813

算法

知道了構造方式、接下來的只是土法煉鋼。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
...
//生成 nxn 空間
map[n][n];

//奇數方陣大小
odd_size = n/2;

//構造奇數方陣
odd_magic = magic(odd_size);

//組合子方陣
for(int x=0; x<odd_size; x++)
for(int y=0; y<odd_size; y++)
{
//組合 A 子方陣
map[x][y] = odd_magic[x][y];
//組合 B 子方陣
map[x+(n/2)][y] = odd_magic[x][y] + 2*pow(odd_size, 2);
//組合 C 子方陣
map[x][y+(n/2)] = odd_magic[x][y] + 3*pow(odd_size, 2);
//組合 D 子方陣
map[x+(n/2)][y+(n/2)] = odd_magic[x][y] + 1*pow(odd_size, 2);
}

//計算 k 值
k = (n - 2)/4;

//交換左上角區塊
for(int x=0; x<k; x++)
for(int y=0; y<k; y++)
swap(map[x][y], map[x][y+odd_size]);

//交換左下角區塊
for(int x=0; x<k; x++)
for(int y=0; y<k; y++)
swap(map[x][odd_size-y], map[x][n-y]);

//交換中間區塊
for(int x=0; x<k; x++)
swap(map[k+x][odd_size/2], map[k+x][n-(odd_size/2)]);

//交換右邊的(k-1)區塊
pos = oddsize + (odd_size/2);
for(int x=pos; x<pos+k-1; x++)
for(int y=0; y<odd_size; y++)
swap(map[x][y], map[x][y+odd_size]);
...

演示

0%