第24講 特殊種法で魔方陣を超高速に自動生成する
第６話 プログラム解説
お約束の通り、ここではプログラムの解説を行います。
コード主要部分を再掲しましょう。
int f(int g,int m[10][10],int n,int* p,int* q,int cn){
int i,j,x,y;
x=p[g];
y=q[g];
for(i=1;i<=n;i++){
m[y][x]=i;
if(g>0){
if(g<n){
for(j=0;j<g;j++){
if(m[j][j]==m[y][x])goto tobi;
}
}
}
if(x==n-1-y && x!=y){
for(j=0;j<y;j++){
if(m[j][n-1-j]==m[y][x])goto tobi;
}
if(m[x][x]==m[y][x])goto tobi;
if(m[y][y]==m[y][x])goto tobi;
if(n%2==1)if(m[n/2][n/2]==m[y][x])goto tobi;
}
if(x!=y && x!=n-1-y){
for(j=0;j<x;j++){
if(m[y][j]==m[y][x])goto tobi;
}
for(j=0;j<y;j++){
if(m[j][x]==m[y][x])goto tobi;
}
if(m[y][y]==m[y][x])goto tobi;
if(m[x][x]==m[y][x])goto tobi;
if(m[y][n-1-y]==m[y][x])goto tobi;
if(m[n-1-x][x]==m[y][x])goto tobi;
}
if(g+1<n*n){
cn=f(g+1,m,n,p,q,cn);
//if(cn==100)return(cn);
}
else{
h(m,n);
cout<<endl<<endl;
//if(cn==100)return(cn);
cn++;
}
tobi:;
}
return(cn);
}
このコードの中で皆さんにとって、
1番理解に苦しむところは、
if(x==n-1-y && x!=y){
for(j=0;j<y;j++){
if(m[j][n-1-j]==m[y][x])goto tobi;
}
if(m[x][x]==m[y][x])goto tobi;
if(m[y][y]==m[y][x])goto tobi;
if(n%2==1)if(m[n/2][n/2]==m[y][x])goto tobi;
}
if(x!=y && x!=n-1-y){
for(j=0;j<x;j++){
if(m[y][j]==m[y][x])goto tobi;
}
for(j=0;j<y;j++){
if(m[j][x]==m[y][x])goto tobi;
}
if(m[y][y]==m[y][x])goto tobi;
if(m[x][x]==m[y][x])goto tobi;
if(m[y][n-1-y]==m[y][x])goto tobi;
if(m[n-1-x][x]==m[y][x])goto tobi;
}
の青色のついているところではないでしょうか。
まず、
if(y==n-1-x && y!=x){
for(j=0;j<y;j++){
if(m[j][n-1-j]==m[y][x])goto tobi;
}
if(m[x][x]==m[y][x])goto tobi;
if(m[y][y]==m[y][x])goto tobi;
if(n%2==1)if(m[n/2][n/2]==m[y][x])goto tobi;
}
のピンク
if(m[x][x]==m[y][x])goto tobi;
if(m[y][y]==m[y][x])goto tobi;
から説明しましょう。
ｎが奇数の場合
| □0□ | □*□ | □*□ | * | 5 |
| * | 1 | * | 6 | * |
| * | * | 2 | * | * |
| * | 7 | * | 3 | * |
| * | * | * | * | 4 |
ｎが偶数の場合
| □0□ | □*□ | □*□ | 4 |
| * | 1 | 5 | * |
| * | * | 2 | * |
| * | * | * | 3 |
if(x==n-1-y && x!=y){
のx==n-1-yという条件から上の図のように逆対角線を動いていきます。
ただし、ｎが奇数の場合は水色のセルで交差しますので、
そこは通り過ぎるようにx!=yが入れてあるわけです。
でないとすでに入っているところに数字を入れてしまうことになります。
５次の場合で、トレースで確認してみましょう。
| 0 | 1 | 2 | 3 | 4 | |
| 0 | □0□ | □*□ | □*□ | * | 5 |
| 1 | * | 1 | * | 6 | * |
| 2 | * | * | 2 | * | * |
| 3 | * | 7 | * | 3 | * |
| 4 | 8 | * | * | * | 4 |
紺はｙ(縦)座標を表し、赤はｘ(横）座標に対応しています。
色の対応に注意しながら読んでください。
y=0のとき、x=n-1-y=5-1-0=4
ですから、対応座標は（0，4）で左図の5に対応します。
y=1のとき、x=n-1-y=5-1-1=3
ですから、対応座標は（1，3）で左図の6に対応します。
y=2のとき、x=n-1-y=5-1-2=2
ですから、対応座標は（2，2）で左図の2（水色のセル）に対応しますが、
禁則x!=yに反しますので、この場合はif文が実行されませんので、
水色のセルを飛ばすことになります。
y=3のとき、x=n-1-y=5-1-3=1
ですから、対応座標は（3，1）で左図の7に対応します。
y=4のとき、x=n-1-y=5-1-4=0
ですから、対応座標は（4，0）で左図の8に対応します。
見事に逆対角線を下降していきますね。
以降は次話で解説します。
