第11話 特殊種法による超高速魔方陣生成ソフトの完成！
を実現するプログラム例
#include<iostream>
#include<ctime>
using namespace std;
int f1(int g,int m1[10][10],int m2[10][10],int a[10][10],int n,int* p,int* q,int cn);
int f2(int g,int m1[10][10],int m2[10][10],int a[10][10],int n,int* p,int* q,int cn);
void h(int m1[10][10],int m2[10][10],int n);
void zh(int n,int *p,int *q);
void sy(int m1[10][10],int n);
void sy1(int m2[10][10],int a[10][10],int n);
void main(){
int m1[10][10],m2[10][10],a[10][10],n,t=0;
while(1){
cout<<"何次魔方陣種を自動生成しますか。"<<endl;
t=1;
if(n!=6)break; else cout<<"6以外の数字を入れて下さい。"<<endl;
}
if(t==1)scanf("%d",&n);
sy(m1,n);
int p[100],q[100];
clock_t hj,ow;
hj=clock();
zh(n,p,q);
cout<<n<<"次魔方陣種が"<<endl<<f1(0,m1,m2,a,n,p,q,0)<<"個できました。"<<endl;
ow=clock();
cout<<"魔方陣種生成にかかった時間は"<<(double)(ow-hj)/1000<<"秒です。"<<endl;
cout<<"プロジェクト終了"<<endl;
}
void sy(int m1[10][10],int n){
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++){
m1[i][j]=0;
}
}
void sy1(int m2[10][10],int a[10][10],int n){
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++){
m2[i][j]=0;
a[i][j]=0;
}
}
void zh(int n,int *p,int *q){
int i,j,cn;
int a[10][10];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=-1;
for(i=0;i<n;i++)a[i][i]=i;
cn=n;
for(i=0;i<n;i++){
if(a[i][n-1-i]==-1){
a[i][n-1-i]=cn;
cn++;
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if(a[i][j]==-1){
a[i][j]=cn;
cn++;
}
}
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
p[a[i][j]]=j;
q[a[i][j]]=i;
}
}
}
int f1(int g,int m1[10][10],int m2[10][10],int a[10][10],int n,int* p,int* q,int cn){
int i,j,x,y,ht;
x=p[g];
y=q[g];
for(i=1;i<=n;i++){
m1[y][x]=i;
if(g>0){
if(g<n){
for(j=0;j<g;j++){
if(m1[j][j]==m1[y][x])goto tobi;
}
}
}
if(x==n-1-y && x!=y){
for(j=0;j<y;j++){
if(m1[j][n-1-j]==m1[y][x])goto tobi;
}
if(m1[x][x]==m1[y][x])goto tobi;
if(m1[y][y]==m1[y][x])goto tobi;
if(n%2==1)if(m1[n/2][n/2]==m1[y][x])goto tobi;
}
if(x!=y && x!=n-1-y){
for(j=0;j<x;j++){
if(m1[y][j]==m1[y][x])goto tobi;
}
for(j=0;j<y;j++){
if(m1[j][x]==m1[y][x])goto tobi;
}
if(m1[y][y]==m1[y][x])goto tobi;
if(m1[x][x]==m1[y][x])goto tobi;
if(m1[y][n-1-y]==m1[y][x])goto tobi;
if(m1[n-1-x][x]==m1[y][x])goto tobi;
}
if(g+1<n*n){
cn=f1(g+1,m1,m2,a,n,p,q,cn);
//if(cn==100)return(cn);
}
else{
sy1(m2,a,n);
cn=f2(0,m1,m2,a,n,p,q,cn);
}
tobi:;
}
return(cn);
}
int f2(int g,int m1[10][10],int m2[10][10],int a[10][10],int n,int* p,int* q,int cn){
int i,j,x,y,ht;
x=p[g];
y=q[g];
for(i=1;i<=n;i++){
m2[y][x]=i;
ht=0;
if(a[m1[y][x]][m2[y][x]]==1)goto tobi;
ht=1;
a[m1[y][x]][m2[y][x]]=1;
if(g>0){
if(g<n){
for(j=0;j<g;j++){
if(m2[j][j]==m2[y][x])goto tobi;
}
}
}
if(x==n-1-y && x!=y){
for(j=0;j<y;j++){
if(m2[j][n-1-j]==m2[y][x])goto tobi;
}
if(m2[x][x]==m2[y][x])goto tobi;
if(m2[y][y]==m2[y][x])goto tobi;
if(n%2==1)if(m2[n/2][n/2]==m2[y][x])goto tobi;
}
if(x!=y && x!=n-1-y){
for(j=0;j<x;j++){
if(m2[y][j]==m2[y][x])goto tobi;
}
for(j=0;j<y;j++){
if(m2[j][x]==m2[y][x])goto tobi;
}
if(m2[y][y]==m2[y][x])goto tobi;
if(m2[x][x]==m2[y][x])goto tobi;
if(m2[y][n-1-y]==m2[y][x])goto tobi;
if(m2[n-1-x][x]==m2[y][x])goto tobi;
}
if(g+1<n*n){
cn=f2(g+1,m1,m2,a,n,p,q,cn);
//if(cn==100)return(cn);
}
else{
h(m1,m2,n);
cout<<endl<<endl;
//if(cn==100)return(cn);
cn++;
}
tobi:;
if(ht==1)a[m1[y][x]][m2[y][x]]=0;
}
return(cn);
}
void h(int m1[10][10],int m2[10][10],int n){
int i,j;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
if((m1[i][j]-1)*n+m2[i][j]<10)cout<<"0"<<(m1[i][j]-1)*n+m2[i][j]<<" ";
if((m1[i][j]-1)*n+m2[i][j]>=10)cout<<(m1[i][j]-1)*n+m2[i][j]<<" ";
}
cout<<endl;
}
}
参考ダウンロード添付ファイル
