第20講 魔方陣汎用的生成プログラムVer.3＝末項確定法
第３話 Ver.3（末項確定法）最適シード値実験完成コード
Ver.3（末項確定法）最適シード値及び飛び値実験完成コード
import java.io.*;
import java.util.*;
public class mj {
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;
static double hj,ow;
static int t=1;
static long s=0;
static double mn=40;
static char kh=0;
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());
*/
n=6;
z();
int i;
for(s=1000;s<2000;s++){
System.out.print ("s=" + s + " ");
kh=0;
if(n==5){
for(i=0;i<8;i++){
if(i==0)t=1;
if(i==1)t=3;
if(i==2)t=7;
if(i==3)t=11;
if(i==4)t=13;
if(i==5)t=17;
if(i==6)t=19;
if(i==7)t=23;
hj = System.currentTimeMillis();
cn=0;
f(0);
}
}
if(n==6){ //実験の結果t=1のときが最速であることがわかっているので、t=1にのみ限定して実験
hj = System.currentTimeMillis();
cn=0;
f(0);
}
if(n==7){//実験では、1個あたり平均２秒以内できる最適シード値及び最適飛び値は発見できなかった。
for(i=0;i<14;i++){
if(i==0)t=1;
if(i==1)t=3;
if(i==2)t=5;
if(i==3)t=11;
if(i==4)t=13;
if(i==5)t=17;
if(i==6)t=19;
if(i==7)t=23;
if(i==8)t=29;
if(i==9)t=31;
if(i==10)t=37;
if(i==11)t=41;
if(i==12)t=43;
if(i==13)t=47;
hj = System.currentTimeMillis();
cn=0;
f(0);
}
}
}
/*
ow = System.currentTimeMillis();
System.out.println();
System.out.println(n+"次魔方陣が"+cn+"個できました。");
System.out.println("魔方陣の探索にかかった時間は"+(ow-hj)/1000+"秒です。");
*/
}
public static void z(){
int i,j,p;
int[][] a=new int[20][20];
for(i=0;i<n;i++){
for(j=0;j<n;j++){
a[i][j]=n*n;
}
}
for(i=0;i<n;i++){
a[i][i]=i;
}
p=n;
for(i=0;i<n;i++){
if(a[i][n-1-i]==n*n){
a[i][n-1-i]=p;
p++;
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(a[i][j]==n*n){
a[i][j]=p;
p++;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
y[a[i][j]]=i;
x[a[i][j]]=j;
}
}
}
public static void f(int g){
if(cn>9)return;
ow = System.currentTimeMillis();
if((ow-hj)/1000>mn)return;
if(y[g]==n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
ow = System.currentTimeMillis();
if((ow-hj)/1000>mn)return;
return;
}
if(y[g]==n-1 && x[g]==0){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][n-1-i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
ow = System.currentTimeMillis();
if((ow-hj)/1000>mn)return;
return;
}
if(y[g]==0 && x[g]==n-2){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[y[g]][i];
w+=m[y[g]][n-1];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
ow = System.currentTimeMillis();
if((ow-hj)/1000>mn)return;
return;
}
if(y[g]==n-2 && x[g]==0){
int i,w=0;
for(i=0;i<n-2;i++)w+=m[i][x[g]];
w+=m[n-1][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
ow = System.currentTimeMillis();
if((ow-hj)/1000>mn)return;
return;
}
if(y[g]>0 && y[g]<n-1 && x[g]==n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[y[g]][i];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
f(g+1);
if(cn>9)return;
ow = System.currentTimeMillis();
if((ow-hj)/1000>mn)return;
return;
}
if(y[g]==n-1 && x[g]>0 && x[g]<n-1){
int i,w=0;
for(i=0;i<n-1;i++)w+=m[i][x[g]];
int sa;
sa=n*(n*n+1)/2-w;
if(sa<=0 || sa>n*n)return;
for(i=0;i<g;i++)if(sa==m[y[i]][x[i]])return;
m[y[g]][x[g]]=sa;
if(g+1<n*n){
f(g+1);
if(cn>9)return;
ow = System.currentTimeMillis();
if((ow-hj)/1000>mn)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>9){
ow = System.currentTimeMillis();
if(mn>(ow-hj)/1000){
mn=(ow-hj)/1000;
if(kh==0)System.out.println();
System.out.println(" s="+s+" t="+t+" "+" cn="+cn+" "+mn+"秒です。");
}
kh=1;
return;
}
}
return;
}
int i,j,h,ii,iii;
ii=0;
if(n!=3 && n!=4){
Random r = new Random(s);
ii=(int)(r.nextInt(n*n));
}
for(i=1;i<n*n+1;i++){
h=1;
iii=(t*i+ii)%(n*n)+1;
m[y[g]][x[g]]=iii;
for(j=0;j<g;j++){
if(m[y[g]][x[g]]==m[y[j]][x[j]]){
h=0;
}
}
if(h==1)f(g+1);
if(cn>9)return;
ow = System.currentTimeMillis();
if((ow-hj)/1000>mn)return;
}
}
}
実験したい方は
ダウンロード用Javaテキストファイル
クリックして開いて、コピーペーストでTeraPadに貼り付けて、
mj.javaの名前で保存してください。
それをコンパイル・実行すれば、実験ができます。
コードの
for(s=1000;s<2000;s++){
System.out.print ("s=" + s + " ");
kh=0;
if(n==5){
for(i=0;i<8;i++){
if(i==0)t=1;
if(i==1)t=3;
if(i==2)t=7;
if(i==3)t=11;
if(i==4)t=13;
if(i==5)t=17;
if(i==6)t=19;
if(i==7)t=23;
hj = System.currentTimeMillis();
cn=0;
f(0);
}
}
if(n==6){ //実験の結果t=1のときが最速であることがわかっているので、t=1にのみ限定して実験
hj = System.currentTimeMillis();
cn=0;
f(0);
}
if(n==7){//実験では、1個あたり平均２秒以内できる最適シード値及び最適飛び値は発見できなかった。
for(i=0;i<14;i++){
if(i==0)t=1;
if(i==1)t=3;
if(i==2)t=5;
if(i==3)t=11;
if(i==4)t=13;
if(i==5)t=17;
if(i==6)t=19;
if(i==7)t=23;
if(i==8)t=29;
if(i==9)t=31;
if(i==10)t=37;
if(i==11)t=41;
if(i==12)t=43;
if(i==13)t=47;
hj = System.currentTimeMillis();
cn=0;
f(0);
}
}
}
の部分などををいろいろ工夫して実験してみてください。
ひょっとしたら７次魔方陣も１個平均２秒以内の最適シード値および最適飛び値が見つかるかもしれません。
第２話へ 第４話へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 入門 C++ 入門
基礎から応用まで第１部
初心者のための VC++による C言語 入門 C++ 入門
基礎から応用まで第２部
初心者のための
VC++による C言語 入門 C++ 入門 基礎から応用まで第３部
