第１７講 普遍版魔方陣自動生成プログラムの高速化
第６話 ランダム版解答例
#include<iostream>
using namespace std;
using namespace System;
void f0();
void f1(int g);
void f2();
int n,cn;
int a[10][10],x[100],y[100];
int main(){
cout<<"何次魔方陣を作成させるのかキーボードから入力してください。"<<endl;
cout<<"次数＝";
scanf("%d",&n);
DateTime^ hj=DateTime::Now;
cn=0;
f0();
f1(0);
cout<<n<<"次魔方陣が"<<cn<<"個できました。"<<endl;
DateTime^ ow=DateTime::Now;
TimeSpan sa=ow->Subtract(*hj);
cout<<"計算時間は"<<sa.TotalSeconds<<"秒です。"<<endl;
/*
int i,j,c[10][10];
for(i=0;i<n*n;i++){
c[y[i]][x[i]]=i;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(c[i][j]<10)cout<<" "<<c[i][j]<<" ";
if(c[i][j]>=10)cout<<c[i][j]<<" ";
}
cout<<endl;
}
*/
}
void f0(){
int i,j,c=0;
int b[10][10];
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;
}
c=n-1;
for(i=0;i<n;i++){
if(b[i][n-1-i]==-1){
c++;
b[i][n-1-i]=c;
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(b[i][j]==-1){
c++;
b[i][j]=c;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
x[b[i][j]]=j;
y[b[i][j]]=i;
}
}
}
void f1(int g){
int i,j,h,w,ii,iii;
rand(); //rand()の無駄打ち rand()の発生順番を変えるため
ii=rand()%(n*n);
for(i=1;i<n*n+1;i++){
iii=(ii+i)%(n*n)+1;
a[y[g]][x[g]]=iii;
h=1;
if(g>0){
for(j=0;j<g;j++){
if(a[y[g]][x[g]]==a[y[j]][x[j]]){
h=0;
break;
}
}
}
if(h==1 && y[g]==n-1 && x[g]==n-1){
w=0;
for(j=0;j<n;j++){
w+=a[j][j];
}
if(w!=n*(n*n+1)/2)h=0;
}
if(h==1 && y[g]==n-1 && x[g]==0){
w=0;
for(j=0;j<n;j++){
w+=a[n-1-j][j];
}
if(w!=n*(n*n+1)/2)h=0;
}
if(h==1 && y[g]==0 && x[g]==n-2){
w=0;
for(j=0;j<n;j++){
w+=a[y[g]][j];
}
if(w!=n*(n*n+1)/2)h=0;
}
if(h==1 && g>n && x[g]==n-1){
w=0;
for(j=0;j<n;j++){
w+=a[y[g]][j];
}
if(w!=n*(n*n+1)/2)h=0;
}
if(h==1 && y[g]==n-2 && x[g]==0){
w=0;
for(j=0;j<n;j++){
w+=a[j][x[g]];
}
if(w!=n*(n*n+1)/2)h=0;
}
if(h==1 && g>2*n-1 && y[g]==n-1){
w=0;
for(j=0;j<n;j++){
w+=a[j][x[g]];
}
if(w!=n*(n*n+1)/2)h=0;
}
if(h==1){
if(g+1<n*n){
f1(g+1);
}
else{
cn++;
f2();
//if(cn==100)break;
}
}
//if(cn==100)break;
}
}
void f2(){
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(a[i][j]<10)cout<<" "<<a[i][j]<<" ";
if(a[i][j]>=10)cout<<a[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
実行結果例
６次魔方陣の作成に成功しました。
ポイントはrand()の無駄打ちにあります。
無駄打ちの回数を工夫すれば７次、８次あたりまでは可能になるかもしれませんが、
かなりの試行錯誤が必要です。
それに、どんなに試行錯誤を繰り返しても１０次魔方陣あたりは歯が立ちません。
１０次魔方陣が作成できるようになるためには、さらにいろいろな工夫が必要になります。
１４，２５，１１，２２，８，１９，５，１６，２，１３，２４，１０，２１，７，１８，４，１５，１，１２，２３，９，２０，６，１７，３という動きをいかに実現するか
の方は
void f1(int g){
int i,j;
int h,w,ii,iii;
rand();
ii=rand()%(n*n);
for(i=1;i<n*n+1;i++){
iii=(ii+11**i)%(n*n)+1;
a[y[g]][x[g]]=iii;
で実現できます。
第５話へ 第18講第１話へ
C言語 C++講義第1部へ
VB講義へ
ＶＢ講義基礎へ
vc++講義へ第1部へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座
初心者のための世界で一番わかりやすいVBA入門講義（基礎から応用まで）
