第20講 一般種法による魔方陣ソフトの高速化
第4話 新しい番号付けのヒントその4

18次の場合

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

では他の色の場合の一般化をしておきましょう。
数列52,83,112,139,164,187,208,227,244の一般項は、
2*n*j+n−j*j−2*j+1であり、
3668,98,126,152,176,198,218,236の一般項は、
2*n*j−j*j−j+2であることを前話で学びました。
したがって、

52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67


等の範囲は2*n*j+n−j*j−2*j+1≦i<2*n*(j+1)−(j+1)*(j+1)−(j+1)+2=2*n*j+2*n−j*j−3*j
(後半のjは一つずれます。例えば、0列目は52≦i<68ですが、52は1番目の項であるのに対して68は2番目の項だからです。)


白い番号(52,83,112など)のときi=2*n*j+n−j*j−2*j+1ですから、
次のように一般化でいます。
for(j=1;j<m+1;j++){               //mはn/2
  if((i>=2*n*j+n-j*j-2*j+1) && (i<2*n*j+2*n-j*j-3*j)){
    x[i]=j-1;
    y[i]=i-(2*n*j+n-j*j-2*j+1)+j;
    if(x[i]>=n-y[i]-1)y[i]++;       //これは逆対角線を跨ぐときの処理
  }
}

















次に、オレンジの場合を考えるために

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

2つの数列252、268,282,294,304,312,318,322と260,275,288,299,308,315,320,323を考えます。
まず、数列252、268,282,294,304,312,318,322の階差は、
(n/2−)+(n/2−)=2*(n/2−=n−2*は表の一番右で、との対応は+m−1すなわち−m+1、またm=n/2)
で初項252=n*n*(3/4)+n/2=3*m*m+mですから、
数列252、268,282,294,304,312,318,322の一般項は、
3*m*m+m+Σ(n−2*k)(kはk=1からk=−1まで)=3*m*m+m+(−1)*(n−

数列260,275,288,299,308,315,320,323の階差は、
(n/2−(−1))+{(n/2−(j−1)−1}=n+1−2*j
で初項260=3*m*m+m+n/2−1=3*m*m+2*m−1なので、一般項は
3*m*m+2*m−1+Σ(n+1−2*j)(kはk=2からk=−1まで)=3*m*m+(j−1)*(n+1−j)

y[i]は表の紺(y)なので+m−1
x[i]は薄緑の番号(252,286,282など)のときi=3*m*m+m+(−1)*(n−)なので、
x[i]=i−(3*m*m+m+(−1)*(n−))+j+m

したがって、オレンジの部分は
for(j=1;j<m;j++){   //mはn/2
  if((i>=3*m*m+m+(j-1)*(n-j)) && (i<3*m*m+j*(n-j))){
    y[i]=j+m-1;
    x[i]=i-(3*m*m+m+(j-1)*(n-j))+j+m;
  }
}
と一般化できます。

最後の薄紫は、iの範囲は
3*m*m+(−1)*(n+1−)≦i<3*m*m+m+(−1)*(n−))(オレンジと薄紫は元々番号が1つずれているのでj+1とする必要がない。)であり、

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


x[i]は表の赤(x)なので+m−2(jは2から始まっているのに注意)、
y[i]は列の最初の番号(260,275,288など)のときi=3*m*m+(−1)*(n+1−)なので、
y[i]=i−(3*m*m+(−1)*(n+1−))++m−1なので
薄紫の部分は
for(j=2;j<m+1;j++){     //mはn/2
  if((i>=3*m*m+(j-1)*(n-(j-1))) && (i<3*m*m+m+(j-1)*(n-j))){
    x[i]=j+m-2;
    y[i]=i-(3*m*m+(j-1)*(n-(j-1)))+j+m-1;
  }
}
と一般化できます。

では次話では、奇数版の番号付けの解答を示しましょう。


第20講第3話へ 第20講第5話へ



VC++講義第1部へ
vb講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座