【魔方陣】読ませる気のないアルゴリズムシリーズ【第三弾】
まずはじめに魔方陣は魔法とはなんら関係ないということを知った。 さて本題にいこう。
魔方陣とは
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
参考: