第16講 魔方陣汎用的生成プログラムへの挑戦
第４話 魔方陣汎用的自動生成プログラムの完成
解答コード例
class x{
public static int[] x=new int[100];
public static int[] y=new int[100];
public static int[][] m=new int[20][20];
public static int n,cn;
public static void main(String args[]) throws IOException {
BufferedReader a = new BufferedReader(new InputStreamReader(System.in));
System.out.println("何次魔方陣を生成させますか。");
System.out.print ("n=");
n=Integer.parseInt(a.readLine());
cn=0;
z();
f(0);
System.out.println();
System.out.println(n+"次魔方陣が"+cn+"個できました。");
}
public static void z(){
int i;
for(i=0;i<n*n;i++){
x[i]=i%n;
y[i]=i/n;
}
}
public static void f(int g){
int i,j,k,h,w;
for(i=1;i<n*n+1;i++){
h=1;
m[y[g]][x[g]]=i;
for(j=0;j<g;j++){
if(m[y[g]][x[g]]==m[y[j]][x[j]]){
h=0;
}
}
if(h==1){
if(x[g]==n-1){
w=0;
for(j=0;j<n;j++){
w+=m[y[g]][j];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(y[g]==n-1){
w=0;
for(j=0;j<n;j++){
w+=m[j][x[g]];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(y[g]==n-1 && x[g]==0){
w=0;
for(j=0;j<n;j++){
w+=m[j][n-1-j];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(y[g]==n-1 && x[g]==n-1){
w=0;
for(j=0;j<n;j++){
w+=m[j][j];
}
if(w!=n*(n*n+1)/2)h=0;
}
}
if(h==1){
if(g+1<n*n){
f(g+1);
//if(cn>20)return;
}
else{
cn++;
for(j=0;j<n;j++){
for(k=0;k<n;k++){
if(m[j][k]<10){
System.out.print(" "+m[j][k]+" ");
}
else{
System.out.print(m[j][k]+" ");
}
}
System.out.println();
}
System.out.println();
//if(cn>20)return;
}
}
}
}
}
実行例
鏡像、中央の線に左右対称、中央の線に上下対称など１つにものに８つあるため、
本当は７０４０÷８＝８８０個です。
このプログラムでは、鏡像なども別のものとしてカウントしています。
別のものとしてカウントすると４次魔方陣は７０４０個あるのです。
尚、５次ではこのプログラムでは歯が立ちません。
ですが、この講の最後のちょっとした改善で５次も１０個程度なら１，２分で出てくるようになります。
しかし、この講のやり方では７次以降はまったく歯が立ちません。
１時間走らせようが、１日間走らせようが１つもでこないでしょう。
１０次魔方陣あたりなら、１年間計算させ続けてもコンピュータは１個も発見できないでしょう。
そして、２６次魔方陣になると１億年探索させてもコンピュータはコマンドプロンプトに１個も表示してくれないでしょう。
ところが、工夫して改良していくと１秒に数百という単位で２６次魔方陣を発見できるようになるのです。
プログラマーの腕が決定的であることがお分かりでしょう。
あなたも最後まで本講義にお付き合いいただければ、
私が開発したプログラムよりずっと高速の魔方陣自動生成プログラムを制作できるようになるでしょう。
ここまで講義についてきた優秀な方ですから、ぼんくらな私よりすばらしいプログラマーになれますよ。
第３話へ 第５話へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 入門 C++ 入門
基礎から応用まで第１部
初心者のための VC++による C言語 入門 C++ 入門
基礎から応用まで第２部
初心者のための
VC++による C言語 入門 C++ 入門 基礎から応用まで第３部
