第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);
}
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 |
for(j=0;j<y;j++){
if(m[j][n-1-j]==m[y][x])goto tobi;
}
によって、逆対角線の重複チェックはされていますが、
実は、水色のセルを除く逆対角線のすべてのセルは、
逆対角線の重複のチェックだけでは不十分です。
何故なら、
| □0□ | □*□ | □*□ | * | 5 |
| * | 1 | * | 6 | * |
| * | * | 2 | * | * |
| * | 7 | * | 3 | * |
| * | * | * | * | 4 |
| □0□ | □*□ | □*□ | 4 |
| * | 1 | 5 | * |
| * | * | 2 | * |
| * | * | * | 3 |
薄緑との重複検査もしなければならないからです。
５次の場合は
| 1 |
と列(縦列）上で重複しないか、
| 3 |
と行(横列)上で重複しないかを
調べないと魔方陣種の条件を満たさなくなります。
魔方陣特殊種は対角線・逆対角線・行・列のいずれでも重複してはならないからです。
４次の場合は
| 1 |
と行(横列）上で、
| 2 |
と列(縦列）上で重ならないかを
テストしないといけないわけです。
再び、５次の場合で、トレースで確認してみましょう。
| 0 | 1 | 2 | 3 | 4 | |
| 0 | □0□ | □*□ | □*□ | * | 5 |
| 1 | * | 1 | * | 6 | * |
| 2 | * | * | 2 | * | * |
| 3 | * | 7 | * | 3 | * |
| 4 | * | * | * | * | 4 |
if(m[x][x]==m[y][x])goto tobi;
if(m[y][y]==m[y][x])goto tobi;
| 7 |
のセルの場合には、
y=3，x=1ですから、
if(m[1][1]==m[3][1])goto tobi;
if(m[3][3]==m[3][1])goto tobi;
となり、m[1][1]は座標（1，1）に対応しますから、
| 1 |
ですし、
m[3][3]は座標（3，3）に対応しますから、
| 3 |
に対応しています。
ですから、
| 1 |
と列(縦列）上で重複しないか、
| 3 |
と行(横列)上で重複しないかを
を調べ重複している場合には、
goto tobi; が実行されているわけです。
ｎが奇数の場合ときの
| 2 |
の意味を説明しましょう。
| □0□ | □*□ | □*□ | * | 5 |
| * | 1 | * | * | * |
| * | * | 2 | * | * |
| * | * | * | 3 | * |
| * | * | * | * | 4 |
黄色いセルに数字を入れるとき、
水色のセルと重複テストをしなければなりません。
何故なら、
for(j=0;j<y;j++){
if(m[j][n-1-j]==m[y][x])goto tobi;
}
は、
| □0□ | □*□ | □*□ | * | 5 |
| * | 1 | * | 6 | * |
| * | * | 2 | * | * |
| * | * | * | 3 | * |
| * | * | * | * | 4 |
1つ手前との重複検査しかしていません。
例えば、右図の6は5との重複チェックしかしてませんよね。
ですが、2のセルの数字と重なっていないかは調べないと、
逆対角線上で重複してしまう可能性が残ります。
では、何故if(n%2==1)と奇数の場合にみに、
中央との重複を検査しているのでしょうか。
理由は簡単です。
偶数の場合には、
| □0□ | □*□ | □*□ | 4 |
| * | 1 | 5 | * |
| * | * | 2 | * |
| * | * | * | 3 |
対角線と逆対角線が交差しないからです。
奇数の場合には、
中央のセル=水色のセル
が存在するのに対して、
偶数の場合には存在しません。
ですから、中央との重複は気にする必要がないのです。
以上の説明を聞くと
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(m[y][y]==m[y][x])goto tobi;
if(m[x][x]==m[y][x])goto tobi;
の部分はもうお分かりではないでしょうか。
| □0□ | □9□ | □*□ | * | 5 |
| * | 1 | * | 6 | * |
| * | * | 2 | * | * |
| * | 7 | * | 3 | * |
| 8 | * | * | * | 4 |
| □0□ | □8□ | □*□ | 4 |
| * | 1 | 5 | * |
| * | 6 | 2 | * |
| 7 | * | * | 3 |
薄緑との重複チェックです。
とすれば、
if(m[y][n-1-y]==m[y][x])goto tobi;
if(m[n-1-x][x]==m[y][x])goto tobi;
は予想がつきますね。
| □0□ | □9□ | □*□ | * | 5 |
| * | 1 | * | 6 | * |
| * | * | 2 | * | * |
| * | 7 | * | 3 | * |
| 8 | * | * | * | 4 |
| □0□ | □8□ | □*□ | 4 |
| * | 1 | 5 | * |
| * | 6 | 2 | * |
| 7 | * | * | 3 |
水色との重複を調べているのです。
