第８講 for文・if文・配列・ポインタを総動員して３次魔方陣の自動生成に挑戦する！
第９話 魔方陣自動生成改良版

３次魔方陣自動生成改良版
#include<iostream>
#include <time.h>
using namespace std;
int f(int *x,int cn);
void g(int *x);
void main(){
　　 int x[9];
　　 int y;
　　 clock_t hj,ow;
　　 hj=clock();
　　 y=f(x,0);
　　 ow=clock();
　　 cout<<endl<<"3次魔方陣総数は"<<y<<endl;
　　 cout<<"魔方陣全解を生成するのにかかった時間は"<<(double)(ow-hj)/1000<<"秒です。"<<endl;
}

int f(int *x,int cn){
　int i,j,k,l,m,n,o,p,q,r,w;
　for(i=1;i<10;i++){
　　x[0]=i;
　　for(j=1;j<10;j++){
　　　x[1]=j;
　　　if(x[1]==x[0])goto tobi1;
　　　for(k=1;k<10;k++){
　　　　x[2]=k;
　　　　for(m=0;m<2;m++)if(x[2]==x[m])goto tobi2;
　　　　w=0;
　　　　for(m=0;m<3;m++)w=w+x[m];　//1行目合計算出
　　　　if(w!=15)goto tobi2;
　　　　for(l=1;l<10;l++){
　　　　　x[3]=l;
　　　　　for(m=0;m<3;m++)if(x[3]==x[m])goto tobi3;
　　　　　for(n=1;n<10;n++){
　　　　　　x[4]=n;
　　　　　　for(m=0;m<4;m++)if(x[4]==x[m])goto tobi4;
　　　　　　for(o=1;o<10;o++){
　　　　　　　x[5]=o;
　　　　　　　for(m=0;m<5;m++)if(x[5]==x[m])goto tobi5;
　　　　　　　w=0;
　　　　　　　for(m=3;m<6;m++)w=w+x[m];　//２行目合計算出
　　　　　　　if(w!=15)goto tobi5;
　　　　　　　for(p=1;p<10;p++){
　　　　　　　　x[6]=p;
　　　　　　　　for(m=0;m<6;m++)if(x[6]==x[m])goto tobi6;
　　　　　　　　w=0;
　　　　　　　　for(m=0;m<9;m=m+3)w=w+x[m];　//1列目合計算出
　　　　　　　　if(w!=15)goto tobi6;
　　　　　　　　w=0;
　　　　　　　　for(m=2;m<7;m=m+2)w=w+x[m];　//右下がり対角線合計算出
　　　　　　　　if(w!=15)goto tobi6;
　　　　　　　　for(q=1;q<10;q++){
　　　　　　　　　x[7]=q;
　　　　　　　　　for(m=0;m<7;m++)if(x[7]==x[m])goto tobi7;
　　　　　　　　　w=0;
　　　　　　　　　for(m=1;m<9;m=m+3)w=w+x[m];　//２列目合計算出
　　　　　　　　　if(w!=15)goto tobi7;
　　　　　　　　　for(r=1;r<10;r++){
　　　　　　　　　　x[8]=r;
　　　　　　　　　　for(m=0;m<8;m++)if(x[8]==x[m])goto tobi8;
　　　　　　　　　　w=0;
　　　　　　　　　　for(m=6;m<9;m++)w=w+x[m];　//３行目合計算出
　　　　　　　　　　if(w!=15)goto tobi8;
　　　　　　　　　　w=0;
　　　　　　　　　　for(m=2;m<9;m=m+3)w=w+x[m];　//３列目合計算出
　　　　　　　　　　if(w!=15)goto tobi8;
　　　　　　　　　　w=0;
　　　　　　　　　　for(m=0;m<9;m=m+4)w=w+x[m];　//右上がり対角線合計算出
　　　　　　　　　　if(w!=15)goto tobi8;
　　　　　　　　　　g(x);
　　　　　　　　　　cn++;
　　　　　　　　　　tobi8:;
　　　　　　　　　}
　　　　　　　　　tobi7:;
　　　　　　　　}
　　　　　　　　tobi6:;
　　　　　　　}
　　　　　　　tobi5:;
　　　　　　}
　　　　　　tobi4:;
　　　　　}
　　　　　tobi3:;
　　　　}
　　　　tobi2:;
　　　}
　　　tobi1:;
　　}
　}
　return(cn);
}

void g(int *x){
　　 for(int i=0;i<9;i++){
　　　　　cout<<x[i]<<" ";
　　　　　if(i%3==2)cout<<endl;
　　 }
　　 cout<<endl;
}

改良によって100倍以上高速になりました。
時間は、0秒と表示される場合の方が多く、
平均すると0.001未満であることは確実です。
ですから、150倍程度は速くなっています。
無駄な検索をしないことが大きいことが分かります。

４次魔方陣でも５次魔方陣でも、
for文をネスト（入れ子式に入れる）していけば、
できますが、４次の段階で１６次元ループ、
５次で２５次元ループですから、
for文ではとてもやる気は起きません。
それに、今回の方法では５次辺りではもう歯が立ちません。
数万倍、数億倍、数兆倍、数京倍と
高速化していかないと高次魔方陣は手も足も出ないのです。
for文を粘り強くネストして６次魔方陣生成ソフトを作ったとしても、
今回の方法では１個作り出すのに、数時間はかかるでしょう。
ですが、私が作った最速のプログラムなら、
２６次魔方陣でも１秒に１００個の単位で、
６次魔方陣なら１秒に数万個の単位で生成可能です。
このようなプログラムを実現するためには、
本当に多くのアイデアが必要です。

４次以上の高次魔方陣を自動生成させるには、
第９講で学ぶ関数の再帰的使用という手法が必要です。
関数の再帰的使用を使えば、１万次元ループも簡単に実現できますし、
１００次魔方陣の自動生成も可能になります。
次講の関数の再帰的使用に進む前に、
最後の改良を加えます。
配列を１次元配列x[9]にしてしまったために、
行の条件を調べるときには、
　　　　x[2]=k;
　　　　for(m=0;m<2;m++)if(x[2]==x[m])goto tobi2;
　　　　w=0;
　　　　for(m=0;m<3;m++)w=w+x[m];
　　　　if(w!=15)goto tobi2;
　　　　　　　　　　　・
　　　　　　　　　　　・
　　　　　　　x[5]=o;
　　　　　　　for(m=0;m<5;m++)if(x[5]==x[m])goto tobi5;
　　　　　　　w=0;
　　　　　　　for(m=3;m<6;m++)w=w+x[m];
　　　　　　　if(w!=15)goto tobi5;
　　　　　　　　　　　　　・
　　　　　　　　　　　　　・
　　　　　　　　　　x[8]=r;
　　　　　　　　　　for(m=0;m<8;m++)if(x[8]==x[m])goto tobi8;
　　　　　　　　　　w=0;
　　　　　　　　　　for(m=6;m<9;m++)w=w+x[m];
　　　　　　　　　　if(w!=15)goto tobi8;
列の条件を調べるときには
　　　　　　　　x[6]=p;
　　　　　　　　　　　　・
　　　　　　　　w=0;
　　　　　　　　for(m=0;m<9;m=m+3)w=w+x[m];
　　　　　　　　if(w!=15)goto tobi6;
　　　　　　　　　　　　　　・
　　　　　　　　　　　　　　・
　　　　　　　　　x[7]=q;
　　　　　　　　　for(m=0;m<7;m++)if(x[7]==x[m])goto tobi7;
　　　　　　　　　w=0;
　　　　　　　　　for(m=1;m<9;m=m+3)w=w+x[m];
　　　　　　　　　if(w!=15)goto tobi7;
　　　　　　　　　　　　　　　・
　　　　　　　　　　　　　　　・
　　　　　　　　　　x[8]=r;
　　　　　　　　　　　　　　　・
　　　　　　　　　　w=0;　
　　　　　　　　　　for(m=2;m<9;m=m+3)w=w+x[m];
　　　　　　　　　　if(w!=15)goto tobi8;
対角線の条件を調べるのに
　　　　　　　　x[6]=p;
　　　　　　　　　　・
　　　　　　　　w=0;
　　　　　　　　for(m=2;m<7;m=m+2)w=w+x[m];
　　　　　　　　if(w!=15)goto tobi6;
　　　　　　　　　　　　　・
　　　　　　　　　　　　　・
　　　　　　　　　　x[8]=r;
　　　　　　　　　　　　　・
　　　　　　　　　　w=0;
　　　　　　　　　　for(m=0;m<9;m=m+4)w=w+x[m];
　　　　　　　　　　if(w!=15)goto tobi8;
と、if文が
if(m=0;m<3;m++)w=w+x[m];
if(m=3;m<6;m++)w=w+x[m];
if(m=6;m<9;m++)w=w+x[m];
（以上行の条件）
if(m=0;m<9;m=m+3)w=w+x[m];
if(m=1;m<9;m=m+3)w=w+x[m];
if(m=2;m<9;m=m+3)w=w+x[m];
（以上列の条件）
if(m=2;m<7;m=m+2)w=w+x[m];
if(m=0;m<9;m=m+4)w=w+x[m];
と姿を変えました。

これは、これから様々な魔方陣や数独に挑戦していく際に、
大きな障壁となります。
もし、２次元配列x[3][3]で組んであれば、
w=0;
for(i=0;i<3;i++)w=w+x[*][i];
if(w!=15)goto tobi*
（行の条件）
w=0;
for(i=0;i<3;i++)w=w+x[i][*];
if(w!=15)goto tobi*
（列の条件）
w=0;
for(j=0;j<3;j++) w=w+x[i][i];
if(w!=15)goto tobi*
（右下がり対角線の条件）
w=0;
for(j=0;j<3;j++)w=w+x[i][2-i];
if(w!=15)goto tobi*
（右上がり対角線の条件）
とすっきりした形になります。
最後の右上がり対角線の式に？？
の人もたくさんいらっしゃると思います。
i=0～i=2でトレース(コンピュータの動きを追うことをトレースといいます。）
をしてみましょう。
２次元配列を使うと、第７話で掲載した表

は

となります。
i=0とき、x[i][2-i]=x[0][2-0]=x[0][2]
i=1とき、x[i][2-i]=x[1][2-1]=x[1][1]
i=2とき、x[i][2-i]=x[2][2-2]=x[2][0]
ですから、確かに右上がり対角線上を動いていますね。

さて、２次元配列にしてプログラムを組み直して下さい。
その際に、
２次元配列を送るにはポインタにするしかなかったことに注意して下さい。
さらに、for(m=0;m<7;m++)if(x[7]==x[m])goto tobi7; などは
for(m=0;m<7;m++)if(x[2][1]==x[m/3][m%3])goto tobi7;
で実現できることを付け加えておきましょう。
念のためにこれの動きもトレースしておきます。
m=0のとき、x[2][1]==x[m/3][m%3]=x[0/3][0%3]=x[0][0]
m=1のとき、x[2][1]==x[m/3][m%3]=x[1/3][1%3]=x[0][1]
m=2のとき、x[2][1]==x[m/3][m%3]=x[2/3][2%3]=x[0][2]
m=3のとき、x[2][1]==x[m/3][m%3]=x[3/3][3%3]=x[1][0]
m=4のとき、x[2][1]==x[m/3][m%3]=x[4/3][4%3]=x[1][1]
m=5のとき、x[2][1]==x[m/3][m%3]=x[5/3][5%3]=x[1][2]
m=6のとき、x[2][1]==x[m/3][m%3]=x[0/3][0%3]=x[2][0]

確かに、x[2][1]とその前とが比較できていますね。

第８話へ　第10話へ



魔方陣 数独で学ぶ VBA 入門
数独のシンプルな解き方・簡単な解法の研究
VB講義へ
ＶＢ講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 C++ 入門 基礎から応用まで第１部
eclipse java 入門
java 入門 サイト 基礎から応用まで
VC++ C言語 C++ 入門 初心者 基礎から応用まで
本サイトトップへ