import java.io.*;
import java.util.*;
class mh{
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=10000000;
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());
z();
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==10)return;
int i,j,k,h,w,ii,iii;
if(n==6)s=149;
if(n==5)s=462;
Random r = new Random(s);
ii=(int)(r.nextFloat()*(n*n));
if(n==6)t=7;
if(n==5)t=17;
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){
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(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]==0 && x[g]==n-2){
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(x[g]==0 && y[g]==n-2){
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]>0 && y[g]<n-1 && 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(x[g]>0 && x[g]<n-1 && 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(g+1<n*n){
f(g+1);
if(cn==10)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==10)return;
}
}
}
}
}
Ver.2の完成で３個を作るのかかる時間は
５次で２．３秒、６次で４．０秒です。
１個あたりの平均は、それぞれ０．８秒と１．３秒です。
ランダムを入れる前に比べると夢のような数字です。
７次、８次についても実験を重ねれば１０秒以内で１個はできるようになりますが、
今回は実験していませんので、Ver.2は６次までの対応としておきます。
次話で第19講は終わりになりますが、第20講でVer.3へ挑戦します。
Ver.3で可能になる範囲は一気に14次まで広がります。
次数にもよりますが、スピードの倍加はVer.2と比べて、
数万倍から数千万倍にも及びます。
尚、第２０講でJava入門講義第２部は終了となります。
第３部では、今まで扱ってこなかったグラフィックを主テーマにして、
グラフィックを利用したゲームやデータベースなどに挑戦します。
また、第４部ではクラスの継承やマルチスレッドなどについて講義をしたいと考えています。
この講義は、まだまだ続けるつもりですので末永いお付き合いをお願いします。
解説
３次と４次につきましては、ランダムを入れる効果はありませんので、
デフォルトとして
static int t=1;
static long s=0;
としてあります。ランダムを入れ意味はありませんので、シード値は何を選んでもよいのでs=0;としました。
if(n==6)s=149;
if(n==5)s=462;
if(n==6)t=7;
if(n==5)t=7;
はどうしてこのシード値と飛び値を選んだのでしょうか。
実験結果です。シード値sは０から５００まで、飛び値tはｎ*ｎ未満の２以外の素数で実験しました。
６次ですとシード値５０１通り、３６未満の２以外の素数９通りですから、
試行回数は５０１×９＝４５０９通りにも及びますから、
もちろん手動で実験したのではありません。
皆さん、このサイトはプログラミングの学習サイトですよ。
実験自体ももちろん自動化してあります。
では、皆さんfor文を使って実験を自動化することを考えてみてください。
第６話へ 第８話へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第１部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第２部
初心者のための VC++による C言語 入門 C++ 入門 基礎から応用まで第３部
