n阶幻方全解

winxos 发表于 2009-1-5 10:12:18

求指定的n阶幻方全部不同解。（n<100)
这个问题上次在火车上想了一下，笔算了一下3阶应该是8种情况，大概我想到了两种适合编程的思路（不知道对不对），
一、解线性方程组+搜索。
二、将1-n*n的数，分成每组和都为幻和的n组，找到全部的分法，然后将每组内每行的数进行位置调整，得到全部解
不过个人觉得这两种方法运算量太大，想了解下各位的想法。
这方面GXQCN应该是“专家”，不知道有没有好的方法？
==补充=========
不一定要求答案，提供一点理论上可行的思路就行。

无心人 发表于 2009-1-5 10:15:53

5以上很难
4的我做过

无心人 发表于 2009-1-5 10:19:19

http://qzc.zgz.cn/X-huanfang7.htm
================================
幻方的数量研究简介

3阶幻方只有一个。由对称与旋转，有8种形式。

4阶幻方因为幻和是34，可以用穷举法获得所有的幻方。早在1693年，弗兰尼克尔(Bernard Frenicle de Bessy)就已经知道4阶幻方共有880个，经对称可得7040个不同的形式。本站给出了这本人编程得到的这全部4阶幻方880个，同时还有一个Flash软件产生这些幻方。

4 阶泛对角幻方，共有384个，有趣的是，由任一个4阶泛对角幻方出发，经一定的变换，可以得出所有这384个泛对角幻方。近年来，一些学者讨论这个问题。参见徐桂芳等《纯幻方的构造原理与方法》（西安交大出版社，1993），潘凤雏《构造所有4阶泛对角线幻方的统一公式》（合肥工大，大学数学，2005.3）。

5阶幻方的数量，人们原先以为可以类似3，4阶得出，但经过数百年仍无结果。产生5阶幻方有各种方法，除前面介绍的两个方法，还有一些，如拉伊尔法，尔仅用此法就可得出57600种不同的幻方。有人估计总数在130000000（一亿三千万）以上，但很多人不相信。1973年，有人用计算机得出5阶幻方的总数是275 305 224个。

至于6阶和更高阶数的幻方数量，现在仍是研究的课题，并已经有一些了不起的结果

gxqcn 发表于 2009-1-5 10:35:18

幻方更多的是研究其美学性质，比如和谐美、奇异美等。
而对于其数目的有限性一般不做研究，因为它是个天文数字，对于当前的计算能力等同于无限。
所以人们更多的研究如何快速构造、判定存在与否等问题，很少去计数统计，因为尚没有好的理论支持。

我现在可以比较随心所欲地构造幻方，
如果不要求数字的连续性，还可以定制非常美妙的幻方，
比如将一个电话号码或身份证数字分成几段后隐藏在幻方的某行的连续格中。

唉，不碰幻方已多年。

winxos 发表于 2009-1-5 10:50:37

啊，比我想像的多很多啊！

我也觉得比较多，没想到有这么多:L
怪不得网上找不到答案呢！
不好意思出了个这样的题目，那换成大家想点可能可以解决的想法，不一定要解出来。

winxos 发表于 2009-1-5 11:12:52

回复 3# 无心人的帖子

你的那个链接我看了，
跟我以前看过的一些构造方法还不一样呢。

xbtianlang 发表于 2011-9-23 11:56:59

RE: n阶幻方全解

贴一个显示5×5幻方的旋转型程序！

xbtianlang 发表于 2011-9-24 20:27:17

求指定的n阶幻方全部不同解。（n
winxos 发表于 2009-1-5 10:12 http://bbs.emath.ac.cn/images/common/back.gif
据说当年计算全部275305224个5×5幻方花了100个小时，几十年过去了，计算机的发展突飞猛进，而算法的研究却进展不大。按现在计算机的速度，我的算法也要用60多个小时，不过因为能同时运行3个程序，所以也能在24小时以内搞定（配置为酷睿2 四核）。
我是按4角排列组合的，角上4个数共有24种排列，其中8个1组是同构的，实际上只有3种，再加上逆幻方，搜索的范围是总数的16分之1。算法的关键在于剪枝，根据幻和分组的意义不大，因为求出全部满足幻和的组合也不需要1秒钟，所以预先搞定能节约的时间实在有限。
3种幻方分为：交叉型X，12与34交叉；平行型Z，12与34平行；旋转型D，12与34反向。
X：89661808，Z：96617928，D：89025488。合计：275305224。
楼上给出的是旋转型D的显示程序，统计时是关闭显示的！

xbtianlang 发表于 2011-9-24 20:31:36

1234指的是由小到大的四个数，
|    X    |       Z    |       D       |
|       1 3    |    1 2 |    1    2    |
|       4 2    | 3 4 |    4    3    |
简称XZD法。

LZC_314 发表于 2012-3-12 21:02:26

以前看了个生成幻方的程序，不知道谁写的，在给大家看一下（c++的）

#include<iostream.h>
#include <stdio.h>
#include<iomanip.h>
void jishu(int n) //任意奇数阶幻方制作的函数（阶梯法）
{
int p=n-1,q=0,s=1,i,j,t=n-1;
int b;
int a;
for(i=0;i<2*n-1;i++)    //给数组a赋初值
for(j=0;j<2*n-1;j++)
a=0;
while(p<2*n-1)          //从a的中间起向下运动一直到最后
{
{
for(i=p;i>=p+1-n;i--) //根据行的变换，列数每次右移五格
for(j=q;j<q+n;j++)
if(i+j==t)
{
a=s;//每次赋值都加1
s++;
}
}
t+=2;
q++;
p++;
}

for(i=0;i<2*n-1;i++) //把中间框以外的数字按规律填到中间的框内
for(j=0;j<2*n-1;j++)
{
if(i<(n-1)/2&&a!=0) //格子上方的数填入数组中
{
a=a;
}
else if(i>=(3*n-1)/2&&a!=0) //格子下方的数填入数组中
{
a=a;
}
else if(j<(n-1)/2&&a!=0) //格子左方的数填入数组中
{
a=a;
}
else if(j>=(3*n-1)/2&&a!=0) //格子右方的数填入数组中
{
a=a;
}
}
for(i=0;i<n;i++) //用一个新数组把a的中间提取出来
for(j=0;j<n;j++)
{
b=a;
}
for(i=0;i<n;i++) //换行输出，每行5个
{
for(j=0;j<n;j++)
cout<<setw(3)<<b<<" ";
cout<<endl;
}
}
void f1(int n) //设计的一个通用双偶函数
{
int a;
int i,j;
int x,k=1,m=3,t;
t=(n-1)/4;
if(t==0) //即n=4
{
for(i=0;i<=m;i++)       //给数组依次赋初值1，2，3…
for(j=0;j<=m;j++)
{
a=k;k++;
}
for(i=1;i<=2;i++) //用走日字的方法交换数组中的元素
{
x=a;a=a;a=x;
         x=a;a=a;a=x;
}
for(i=0;i<=m;i++) //输出数组
{
for(j=0;j<=m;j++)
      cout<<a<<" ";
cout<<endl;
}goto loop;    //跳到loop
}

for(i=0;i<8;i++)    //给数组赋初值0
for(j=0;j<8;j++)
a=0;
if(n%4==0&&n/4>1)
{
for(i=0;i<2;i++) //取左上角四个格子把主对角线上的元素赋值为1
for(j=0;j<2;j++)
{
if(i==j)
a=1;
}
}
while(t>0)
{
for(i=0;i<2;i++) //水平复制刚才的四格
   for(j=2;j<4;j++)
a=a;
for(i=2;i<4;i++)    //将上述八格水平翻转
for(j=0;j<4;j++)
a=a;


for(i=0;i<n;i++)       //水平对称翻转
for(j=n/2;j<n;j++)
a=a;

for(i=n/2;i<n;i++) //垂直对称翻转          for(j=0;j<n;j++)
a=a;
t--;
}
for(i=0;i<n;i++) //从左上角起，给值为0的元素重新赋值，值为n*i+j+1
for(j=0;j<n;j++)
if(a==0)
a=n*i+j+1;
for(i=n-1;i>=0;i--) //从右下角起，给值为1的元素重新赋值，值为n*n-n*i-j
for(j=n-1;j>=0;j--)
if(a==1)
a=n*n-n*i-j;
for(i=0;i<n;i++) //输出数组
{
for(j=0;j<n;j++)
cout<<setw(3)<<a<<" ";
cout<<endl;
}
loop:;
}
void danou(int n) //设计的一个通用单偶函数
{
int p=n-1,q=0,s=1,i,j,t=n-1,v=n/2;
int a,b,c,d,e;
int m=(n-2)/4;
for(i=0;i<n/2;i++) //给数组赋初值
for(j=0;j<n/2;j++)
a=0;
int x,y;
int max;
int mid;
max=v*v;
mid=v/2;
x=v-1;
y=mid+1;
for(i=0;i<n/2;i++) //将a做一次奇数阶幻方变换
for(j=0;j<n/2;j++)
a=0; //设置初始值是0
a=1;
for(i=2;i<=max;i++)
{
if(x<0&&y>n/2-1)
{
x=0;y=n/2-1;x=x+1; //在最右上角超出
}
if(x<0)
{
x=n/2-1;    //在上方超出
}
if(y>n/2-1) //在右方超出
{
y=0;
}
if(a!=0)
{
x=x+2;y=y-1; //在右上角有数字
}
a=i; //正常附值
x=x-1; //正常附值
y=y+1; //正常附值
}

for(i=0;i<n/2;i++) //给b数组赋值，在a的对应数上加2*v*v
for(j=0;j<n/2;j++)
b=a+2*v*v;
for(i=0;i<n/2;i++) //给c数组赋值，在a的对应数上加v*v
for(j=0;j<n/2;j++)
c=a+v*v;
for(i=0;i<n/2;i++)    //给d数组赋值，在a的对应数上加3*v*v
for(j=0;j<n/2;j++)
d=a+3*v*v;
int temp; //定义交换变量
for(i=0;i<=n/2-1;i++) //将a和d的前面进行交换
for(j=0;j<m;j++)
{
temp=a;
a=d ;
d=temp;
}
   temp=a[(n-2)/4]; //a和d中间一行第一列的数再交换过来，即不交换
   a[(n-2)/4]=d[(n-2)/4];
d[(n-2)/4]=temp;

temp=a[(n-2)/4];    //a和d中间一行第二列的数交换过来
a[(n-2)/4]=d[(n-2)/4];
d[(n-2)/4]=temp;

for(i=0;i<=n/2-1;i++) //将c和b的最后列进行交换
for(j=n/2-1;j>(n-2)/4+1;j--)
{
temp=b;
b=c;
c=temp;
}
for(i=0;i<n/2;i++) //用大数组e【100】【100】把四个小数组拼接起来
for(j=0;j<n/2;j++)
e=a;
for(i=0;i<n;i++)
for(j=n/2;j<n;j++)
e=b;
for(i=n/2;i<n;i++)
for(j=0;j<n/2;j++)
e=d;
for(i=n/2;i<n;i++)
for(j=n/2;j<n;j++)
e=c;
for(i=0;i<n;i++) //输出数组
{
for(j=0;j<n;j++)
cout<<setw(3)<<e<<" ";
cout<<endl;
}
}

void main()//主函数
{ bool f=true;
while(f)
{
int n;                   //界面设计
cout<<endl;
cout<<setw(48)<<"    幻方制作"<<endl;
cout<<endl;
cout<<setw(50)<<"============="<<endl;
cout<<endl;
cout<<setw(50)<<"    1.奇数阶幻方"<<endl;
cout<<setw(50)<<"    2.偶数阶幻方"<<endl;
cout<<endl;
cout<<setw(56)<<"请选择(1或2，0:退出)"<<endl;
int k;
cin>>k;
//int k;
// cin>>k;
switch(k)
{
case 1:
cout<<"请输入奇数n(2<n<=10)"<<endl;
cin>>n;
if(n<3||n>=10||n%2==0)
{
do{
   cout<<"对不起,您的输入有误,请重新来过!"<<endl;
   cin>>n;
   }while(n>=3&&n<10&&n%2!=0);
}
else
jishu(n);
break;
case 2:
cout<<"请输入需要的偶数n(2<n<=10)"<<endl;
cin>>n;
if(n<3||n>10||n%2!=0)
{
do{
            cout<<"对不起,您的输入有误,请重新来过!"<<endl;
   cin>>n;
}while(n>3&&n<=10&&n%2==0);
}
else{
      if(n%4==0)
         f1(n);
         else if(n%2==0&&n%4!=0)
         danou(n);
}
break;
case 0:f=false;break;
default:
cout<<"查无此号"<<endl;
}
}
}

页: [1]

数学研发论坛's Archiver