魔方陣Magic Square | 羊羽手札

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

0% 這個是我們資料結構（DataStructure）的第二次作業，本文紀錄了奇數、雙偶數以及單偶數魔方陣（MagicSquare）的做法。

老實說，上課不斷的聯想到太鼓達人的★9曲「魔方陣-サモン・デルタ-」 魔方陣定義魔方陣定義是這樣的： 每一行（Column）的總和 每一列（Row）的總和 對角線的總和 上面每一個值都相等 這邊採用了直行橫列的說法。

比方說圖1這樣： 接下來我會記錄如何製作魔方陣。

奇數魔方陣奇數的魔方陣是魔方陣中比較簡單的一種，構造方式相當容易。

正常情況下，給定一個$n$在$O(n^2)$時間複雜度內就可以完成。

第一列（Row）中間放「1」 不斷往左上角移動（走出方格從對面出現）、放入下一個數字 如果左上角空間已有數字，則往下放一格 以$3$x$3$魔方陣為例（$n=3$）： 第一步：如圖2在中間上面放「1」 第二步：如圖3不斷往左上走。

同時累進數字。

（這個1從上方跑出方陣、於是2應該在下面。

） 如圖4我們接下來不斷重複。

第三步：如圖5這個3的左上方已經有數字，於是往下放一格。

依照這個步驟繼續完成。

如圖6所示，我們最終就得到一個不錯的方陣。

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

1234567891011121314151617181920212223...//計算下一步的座標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的倍數。

這類型的魔方陣比奇數更複雜一些。

雙偶數的魔方陣的做法： 先按照順序填入 找到主對角線 找到副對角線 把不在對角線上的值依序取下 把取下的值從後面反過來填上 重點在於，何謂主、副對角線呢？這邊的解釋是，任何可以切割成方格的樣子。

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

當$n=4$時，沒有副對角線。

當$n\geq8$時，有副對角線。

算法最麻煩的是、你如何抓對角線呢？讓我們來仔細觀察看看圖9： 不曉得有沒有發現呢？他縱向、橫向的規律是一致的。

然後他對角線上的值有這樣的特性： 位置$(x,y)$ 如果$x\mod4=0$或$3$且$y\mod4=0$或$3$（上方紅色） 如果$x\mod4=1$或$2$且$y\mod4=1$或$2$（上方藍色） 12345678910111213141516171819202122232425...//弄個陣列array=[]//遍歷位置for(xis0towidth)for(yis0toheight){//屬於非對角線的話，推入陣列if(belong(x,y))array.push((x,y));}//翻轉陣列array.reverse();//最後填回for(xis0towidth)for(yis0toheight){//屬於非對角線的話，從陣列中回填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$的形式。

這種方陣的樣貌大致上呈現，如圖10及圖11這樣： 這邊來敘述這種方陣的構成： 先構造一個$n/2$的魔方陣，作為子方陣 拼合4個子方陣（規則下面會說明） 透過$k=(n-2)/4$求出$k$ 搬動方陣內的元素 我們以$n=6$為例子。

首先，我們得構造一個$3$x$3$的魔方陣，如圖12： 接著我們要拚合子方陣。

先看圖13： 總共會把子方陣複製4份貼在$6$x$6$的方陣中。

不過還得加上一個常數：$m\cdot(n/2)^2$ A區塊$m=0$、所以方陣中元素加$0$ B區塊$m=2$、所以方陣中元素加$2\cdot3^2=18$ C區塊$m=3$、所以方陣中元素加$3\cdot3^2=27$ D區塊$m=1$、所以方陣中元素加$1\cdot3^2=9$ 將其累進拚合後： 這樣就拚合了4個子方陣成為一個大的6x6方陣，如圖14。

不過還沒有完成。

我們得搬動一些元素才行。

接著，透過$k=(n-2)/4$求出$k$。

$n=6$代表$k=1$然後把矩陣分成上下兩塊，如圖15： 搬動元素的規則為： 上面區塊的左上角$k$x$k$方陣跟下方換。

上面區塊的左下角$k$x$k$方陣跟下方換。

上面區塊的中間列（Row）從$k$位置向右$k$格跟下方換 上面矩陣的$(n/2)+\lfloorn/4\rfloor$（也就是右半邊的中間）處向右$k-1$格跟下方換 實際標記看看，上面區塊的左上角$k$x$k$方陣跟下方換（$k=1$），如圖16： 上面區塊的左下角$k$x$k$方陣跟下方換（$k=1$），如圖17： 上面區塊的中間列（Row）從$k$位置（綠框）向右$k$格（藍框）跟下方換（$k=1$），如圖18： 注意計算綠框向右$k$格時，綠框自己不算是1格。

上面矩陣的$(n/2)+\lfloorn/4\rfloor$處向右$k-1$格跟下方換，這邊理解一下，雖然看起來很複雜，但$n/2$是子方陣的大小、$(n/2)/2$恰為子方陣大小的一半。

從綠框處（含）、往右$0$格（藍框、因為是$0$而無法顯示）如圖19： 您可以在演示區使用$10$x$10$的魔方陣觀察這一步。

這樣最後得到的，如圖20就是完好的魔方陣了。

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

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647...//生成nxn空間map[n][n];//奇數方陣大小odd_size=n/2;//構造奇數方陣odd_magic=magic(odd_size);//組合子方陣for(intx=0;x<odd_size;x++)for(inty=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(intx=0;x<k;x++)for(inty=0;y<k;y++)swap(map[x][y],map[x][y+odd_size]);//交換左下角區塊for(intx=0;x<k;x++)for(inty=0;y<k;y++)swap(map[x][odd_size-y],map[x][n-y]);//交換中間區塊for(intx=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(intx=pos;x<pos+k-1;x++)for(inty=0;y<odd_size;y++)swap(map[x][y],map[x][y+odd_size]);... 演示 文章目錄 本站概要 1.魔方陣定義2.奇數魔方陣2.1.算法2.2.演示3.雙偶數魔方陣3.1.算法3.2.演示4.單偶數魔方陣4.1.算法4.2.演示 Tinytusnami 羊羽的個人部落格 44 文章 11 分類 GitHub Twitter FBPage YouTube 友站連結 Cyris'sBlog