SwiftyNote

主にSwiftな技術ブログ

【魔方陣】読ませる気のないアルゴリズムシリーズ【第三弾】

まずはじめに魔陣は魔とはなんら関係ないということを知った。 さて本題にいこう。

方陣とは

n×n 個の正方形の方陣に数字を配置し、縦・横・対角線のいずれの列についても、その列の数字の合計が同じになるもののことである。

行や列単位での交換もできるため、その組み合わせ数は膨大にある。

5 * 5の魔方陣については

1970年代から2億7530万5224通り(対称形などをのぞく)存在することが知られている

とある。Nに対する式で書いて欲しい。

実際に、やってみた。(トレビア風 [ソースコード]

#include <iostream>
#include <iomanip>
using namespace std;
// N * Nの魔方陣(ただしN=奇数)
const int N = 3;
int main() {
    int x,y,c=0,a[N][N];
    // 魔方陣の計算
    for(x=-N/2;x<=N/2;x++)for(y=0;y<N;y++)a[(y-x+N)%N][(y+x+N)%N]=++c;
    // 出力
    for(x=0;x<N*N;x++)cout<<setw(3)<<setfill(' ')<<a[x%N][x/N]<<((x+1)%N?" ":"\n");
}

[出力] 3 * 3

4   9   2
3   5   7
8   1   6

9 * 9

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

17 * 17

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

参考:

方陣 - Wikipedia