第２０講 一般種法による魔方陣ソフトの高速化
第３話 仮屋崎さんのエレガントな方法の解説

　　　　　　　void g(int n){
　　　　　　　　　char i,j;

　　　　　　　　　for(i=0;i<n;i++){
　　　　　　　　　　　for(j=0;j<n;j++){
　　　　　　　　　　　　　b[i][j]=-1;
　　　　　　　　　　　}
　　　　　　　　　}
　　　　　　　　　for(i=0;i<n;i++){
　　　　　　　　　　　b[i][i]=i;
　　　　　　　　　}
　　　　　　　　　cn=n;
　　　　　　　　　for(i=0;i<n;i++){
　　　　　　　　　　　if(b[i][n-1-i]==-1){
　　　　　　　　　　　　　b[i][n-1-i]=cn;
　　　　　　　　　　　　　cn++;
　　　　　　　　　　　}
　　　　　　　　　}
　　　　　　　　　g1(n,0,1);
　　　　　　　　　for(i=0;i<n;i++){
　　　　　　　　　　　for(j=0;j<n;j++){
　　　　　　　　　　　　　x[b[i][j]]=j;
　　　　　　　　　　　　　y[b[i][j]]=i;
　　　　　　　　　　　}
　　　　　　　　　}
　　　　　　　}
　　　　　　　void g1(int n,int y,int x){
　　　　　　　　　if(b[y][x]==-1){
　　　　　　　　　　　b[y][x]=cn;
　　　　　　　　　　　cn++;
　　　　　　　　　}
　　　　　　　　　if(x+1<n){
　　　　　　　　　　　g1(n,y,x+1);
　　　　　　　　　}
　　　　　　　　　else{
　　　　　　　　　　　t++;
　　　　　　　　　　　if(t<n){
　　　　　　　　　　　　　g2(n,t,t-1);
　　　　　　　　　　　}
　　　　　　　　　}
　　　　　　　}
　　　　　　　void g2(int n,int y,int x){
　　　　　　　　　if(b[y][x]==-1){
　　　　　　　　　　　b[y][x]=cn;
　　　　　　　　　　　cn++;
　　　　　　　　　}
　　　　　　　　　if(y+1<n){
　　　　　　　　　　　g2(n,y+1,x);
　　　　　　　　　}
　　　　　　　　　else{
　　　　　　　　　　　if(t+1<n){
　　　　　　　　　　　　　g1(n,t,t+1);
　　　　　　　　　　　}
　　　　　　　　　}
　　　　　　　}

解説
　　　　　　　　　for(i=0;i<n;i++){
　　　　　　　　　　　for(j=0;j<n;j++){
　　　　　　　　　　　　　b[i][j]=-1;
　　　　　　　　　　　}
　　　　　　　　　}
　　　　　　　　　for(i=0;i<n;i++){
　　　　　　　　　　　b[i][i]=i;
　　　　　　　　　}
　　　　　　　　　cn=n;
　　　　　　　　　for(i=0;i<n;i++){
　　　　　　　　　　　if(b[i][n-1-i]==-1){
　　　　　　　　　　　　　b[i][n-1-i]=cn;
　　　　　　　　　　　　　cn++;
　　　　　　　　　　　}
　　　　　　　　　}
と
　　　　　　　　　for(i=0;i<n;i++){
　　　　　　　　　　　for(j=0;j<n;j++){
　　　　　　　　　　　　　x[b[i][j]]=j;
　　　　　　　　　　　　　y[b[i][j]]=i;
　　　　　　　　　　　}
　　　　　　　　　}

ピンクは、対角線と逆対角線の番号付けですし、
薄緑は、番号から座標へ関連づけをしています。
薄緑の直前までが座標から番号への関連づけだったのを反転させているのです。
詳しいことは、第17講（再講義）第3話を参照にして下さい。

そして、今回の改訂のメインになるのは、g1とg2です。

g1は行部分（表の紺）を、g2は列部分（表の

）をそれぞれ担当しています。動きを追ってみましょう。

まず、g1(n,0,1);で座標（０，１）すなわち

へと飛びます。g1では最初に何をしているかと申しますと、
　　　if(b[y][x]==-1){
　　　　　 b[y][x]=cn;
　　　　　　　　　　　cn++;
　　　　　　　　　}
b[0][1]が−１のままであるか調べています。
つまり、まだ本来の番号付けがなされていないか、調べています。
もし−１であれば、−１は仮の番号付けなので、本来の番号付けはなされていないことになります。
g1(n,0,1);ではじめて

の世界（座標（０，１））に来たわけですから、当然仮の番号の−１が割り振られています。
そこでif文が実行され、b[y][x]=cn;によって１９の次の番号２０が割り振られ、

となり、
次の行のcn++;によってcnは２１となります。
cnがすでに２０であった理由は、
逆対角線の最後の処理
　　　　　　　　　for(i=0;i<n;i++){
　　　　　　　　　　　if(b[i][n-1-i]==-1){
　　　　　　　　　　　　　b[i][n-1-i]=cn;
　　　　　　　　　　　　　cn++;
　　　　　　　　　　　}
　　　　　　　　　}
によって、座標（９，０）が

となっていて、さらにcn++;により２０となっていたからです。
さて、このif文が実行された後、次のif文
　　　if(x+1<n){
　　　　　　g1(n,y,x+1);
　　　　　　　　　}
　　　　　　　　　else{
　　　　　　　　　　　t++;
　　　　　　　　　　　if(t<n){
　　　　　　　　　　　　　g2(n,t,t-1);
　　　　　　　　　　　}
　　　　　　　　　}
に進みます。x+1は1+1の計算から２です。ですから、x+1<n（ｎは１０）を満たして、
g1(n,y,x+1);が実行され、座標（０，２）の世界

へと飛びます。

のときと同様に処理されて

は

となります。x+1は３ですからx+1<nはまだ満たされていて、g1(n,y,x+1);が実行され

の世界に飛び同様に処理されて、

は

となります。以下同様にして、

となり、座標（０，８）の世界

へ飛び、if文
　　　if(b[y][x]==-1){
　　　　　 b[y][x]=cn;
　　　　　　　　　　　cn++;
　　　　　　　　　}
によって、

は

となります。そして、
　　　　　　　　　if(x+1<n){
　　　　　　　　　　　g1(n,y,x+1);
　　　　　　　　　}
　　　　　　　　　else{
　　　　　　　　　　　t++;
　　　　　　　　　　　if(t<n){
　　　　　　　　　　　　　g2(n,t,t-1);
　　　　　　　　　　　}
　　　　　　　　　}
のとき、x+1は１０（すなわちｎ）ではじめてelse文が実行されまして、
t++;によってtは1となり、if文
　　　　　　　　　　　if(t<n){
　　　　　　　　　　　　　g2(n,t,t-1);
　　　　　　　　　　　}
が実行され、座標（１，０）の世界

へと飛翔します。

は、if文
if(b[y][x]==-1){
　　　b[y][x]=cn;
　　　cn++;
　　　　　　　　　　　}
によって、

となります。
g1とg2の処理は、本質的に同じですが、
g1の横処理に対して、g2は縦処理ですので、下へ進みます。



　　　　　　　　　if(y+1<n){
　　　　　　　　　　　g2(n,y+1,x);
　　　　　　　　　}
のg2(n,y+1,x);に注目すればそれは分かります。

そして、どんどん仮番号−１は本当の番号に変わっていって、

となります。この時点で、y+1は１０（すなわちｎ）となり、
　　　　　　　　　if(y+1<n){
　　　　　　　　　　　g2(n,y+1,x);
　　　　　　　　　}
　　　　　　　　　else{
　　　　　　　　　　　if(t+1<n){
　　　　　　　　　　　　　g1(n,t,t+1);
　　　　　　　　　　　}
　　　　　　　　　}
のelse文が実行され、再びg1の世界すなわち横処理の世界へと進みます。
このようにして、横処理と縦処理が交互に進み、

が実現されるのです。

どうです。これもまさに見事です。すばらしいですね。

もう一つ、仮屋崎さんからメールで寄せられました。
今回紹介したものが、セル単位で進行するのに対して、
行または列単位で次に進む方法を次話で紹介しましょう。
実は、最初に寄せられたものは次話で紹介する行または列単位で進むものだったのですが、
私が熟読しないで早とちりしたものが、今回紹介したセル単位で進行するものだったのです。
早とちりの原因は、さっと読んで何も見ないでプログラミングするという私の学習法にあります。
家でさっと見た後、２日後に記憶のみによって、学校でVBAを使って再現したものが今回紹介したものです。
VBAを使った理由は、学校にはVC++がインストールされていないからです。

第２０講（再講義）第２話へ 　第２０講（再講義）第４話へ

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