幻方

幻方可以使用N阶方阵来表示,方阵的每行、每列以及两条对角线的和都等于常数

任意阶幻方的解法及c++实现

在一个由若干个排列整齐的数组成的正方形中,图中任意一横行、一纵行及对角线的几个数之和都相等,具有这种性质的图表,称为“幻方”。我国古代称为“河图”、“洛书”,又叫“纵横图”。

奇数阶幻方(罗伯法)

奇数阶幻方最经典的填法是罗伯法。填写的方法是:
把1(或最小的数)放在第一行正中; 按以下规律排列剩下的(n×n-1)个数:

1、每一个数放在前一个数的右上一格;
2、如果这个数所要放的格已经超出了顶行那么就把它放在底行,仍然要放在右一列;
3、如果这个数所要放的格已经超出了最右列那么就把它放在最左列,仍然要放在上一行;
4、如果这个数所要放的格已经超出了顶行且超出了最右列,那么就把它放在前一个数的下一行同一列的格内;
5、如果这个数所要放的格已经有数填入,那么就把它放在前一个数的下一行同一列的格内。

例:用该填充方法获得的五阶幻方

双偶数阶幻方(对称交换法)

所谓双偶阶幻方就是当n可以被4整除时的偶阶幻方,即4K阶幻方。在说解法之前我们先说明一个“互补数”定义:就是在 n 阶幻方中,==如果两个数的和等于幻方中最大的数与 1 的和(即 n×n+1),我们称它们为一对互补数== 。如在三阶幻方中,每一对和为 10 的数,是一对互补数 ;在四阶幻方中,每一对和为 17 的数,是一对互补数 。

4阶幻方
(1) 将数字从上到下,从左到右依次填入:

(2) 将对角线上元素换成其互补数:

8阶幻方
(1) 将数字从上到下,从左到右依次填入,并按2*2把它分成4块奇数阶幻方:

(2) 每个小方阵对角线上的数字(如左上角小方阵部分),换成和它互补的数:

单偶数阶幻方(象限对称交换法)

(1)把方阵分为A,B,C,D四个象限,这样每一个象限都是奇数阶。用罗伯法,依次在A象限,D象限,B象限,C象限按奇数阶幻方的填法填数。

(2)从A象限的中间行、中间格开始,按自左向右的方向,标出k格。A象限的其它行则标出最左边的k格。将这些格,和C象限相对位置上的数互换位置。

(3)从B象限的最中间列开始,自右向左,标出k-1列。(注:6阶幻方由于k-1=0,所以不用再作B、D象限的数据交换), 将B象限标出的这些数,和D象限相对位置上的数进行交换,就形成幻方。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dwn(i,a,b) for(int i=(a);i>=(b);--i)
template <typename T>inline void rd(T &x){
    x=0;char c=getchar();int f=0;
    while(!isdigit(c)){f|=c=='-';c=getchar();}
    while(isdigit(c)){x=x*10+(c^48);c=getchar();}
    x=f?-x:x;
}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)
/*****************************************************Header Template*************************************************/
#define N 256
int m[N][N];

inline void OddMagic(int n){
    mem(m,0);//幻方清零
    int x=0, y=n/2;
    rep(i,1,n*n){
        m[x--][y++]=i;//依次沿右上角填充
        if(x<0 && y>n-1){x+=2;y--;}//沿对角线超出
        else if(x<0) x=x+n;                  //沿上边界超出
        else if(y>n-1) y=y-n;                //沿右边界超出
        else if(m[x][y]!=0) {x=x+2; y=y-1;}  //右上角已填充
    }
}

inline void DoubleEvenMagic(int n){                  //双偶数阶幻方
    mem(m,0);
    int x=0,y=0;
    rep(i,1,n*n){
        m[x][y]=i;
        y++;
        if(y>n-1){x++,y-=n;}
    }
    //将幻方分解成m*m个4阶幻方,并将每个4阶幻方的对角线元素换成其互补数
    rep(i,0,n-1)
        rep(j,0,n-1)
            if(i%4==0 && j%4==0)//左对角线
                rep(k,0,3)
                    m[i+k][j+k]=(n*n+1)-m[i+k][j+k];
            else if(i%4==3 && j%4==0)//右对角线
                rep(k,0,3)
                    m[i-k][j+k]=(n*n+1)-m[i-k][j+k];
}

inline void SingleEvenMagic(int n){//单偶数阶幻方
    mem(m,0);
    int n0=n/2;
    OddMagic(n0);//将幻方分解成2*2个奇数阶幻方,调用奇数阶幻方函数填充左上角奇数阶幻方
    rep(i,0,n0-1)
        rep(j,0,n0-1){
            m[i+n0][j+n0]=m[i][j]+n0*n0;       //填充右下角奇数阶幻方
            m[i][j+n0]=m[i+n0][j+n0]+n0*n0;     //填充右上角奇数阶幻方
            m[i+n0][j]=m[i][j+n0]+n0*n0;       //填充左下角奇数阶幻方
        }
    int k=(n-2)/4;                             //满足公式n=4*k+2
    rep(i,0,n0-1)
        rep(j,0,k-1)
            if(i==n0/2) swap(m[i][i+j],m[i+n0][i+j]);   //将左上角幻方最中间元素从左向右的k个元素与左下角幻方相应位置元素交换
            else swap(m[i][j],m[i+n0][j]);              //将左上角幻方除最中间行外的每行前k个元素与左下角幻方相应位置元素交换
    rep(i,0,n0-1)
        for(int j=n0+n0/2;j>n0+n0/2-(k-1);j--)
            swap(m[i][j],m[i+n0][j]);                   //将右上角幻方最中间列起从右向左的k-1列元素与右下角幻方相应位置元素交换
}

inline bool check(int n){
    int cnt=n*(n*n+1)/2;                                //每行每列以及对角线之和
    rep(i,0,n-1){
        int sum_line=0,sum_row=0;
        rep(j,0,n-1){
            sum_row+=m[i][j];
            sum_line+=m[j][i];
        }
        if(sum_row!=cnt || sum_line!=cnt)return false;
    }
    int sum_left=0,sum_right=0;
    rep(i,0,n-1){
        sum_left+=m[i][i];
        sum_right+=m[n-i-1][i];
    }
    if(sum_left!=cnt || sum_right!=cnt) return false;
    return true;
}

inline void print(int n){
    rep(i,0,n-1)
        rep(j,0,n-1)
            if(j==n-1)printf("%-4d\n",m[i][j]);
            else printf("%-4d",m[i][j]);
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        if(n<3)puts("Impossible");
        else if(n&1){OddMagic(n);if(check(n))print(n);}
        else if(!(n%4)){DoubleEvenMagic(n);if(check(n))print(n);}
        else {SingleEvenMagic(n);if(check(n))print(n);}
    }
    return 0;
}
02-01 11:35