JAVA实现幻方

Java
208
0
0
2024-02-19
Spring Boot 打包插件，真是太有用了
上一篇
浅学Spring启用Log4j日志框架
下一篇

幻方 （Magic Square）是一种将数字安排在正方形格子中，使每行、列和对角线上的数字和都相等的方法。

幻方也是一种中国传统游戏。旧时在官府、学堂多见。它是将从一到若干个数的自然数排成纵横各为若干个数的正方形，使在同一行、同一列和同一对角线上的几个数的和都相等。

三阶幻方

​

本篇主聊高阶幻方 构造方法 的java实现

数据结构：以二维数组存放数字

例：上面的三阶幻方数组数据如下（不考虑幻方阶次较高，最大值超过int最大值）

int[][] square = {
{,1,6},
{,5,7},
{,9,2}
};

数据结构有了，怎么去验证一个二阶数组的数据是不是一个有效的幻方构造数据呢？

具体思路就是反正法，默认数据符合幻方数据内容：

/**验证一个二阶数组里的数是不是符合一个幻方的要求*/public static boolean isValidSquare(int[][] nums){
    try {
        //i阶次幻方
        int i = nums.length;
        //行列斜的和为
        int s = (i*i+)*i/2;
        //数据完整性校验数组
        int[]  check  = new int[i*i+1];
        //校验每一行/每一列的和是不是等于s
        for (int x =; x < i; x++) {
            int lineSum =;
            int colSum =;
            for (int y =; y < i; y++) {
                check[nums[x][y]]=nums[x][y];
                lineSum += nums[x][y];
                colSum += nums[y][x];
            }
            if (lineSum!=s || colSum!=s) {
                return false;
            }
        }
        //校验两个对角线的和是否等于s
        int sSum = 0;
        int sSum = 0;
        for (int x =; x < i; x++) {
            sSum += nums[x][x];
            sSum += nums[i-x-1][x];
        }
        if (sSum!=s || s2Sum!=s) {
            return false;
        }
        //校验check数组中是否包含到i*i中的每一个数
        for (int j =; j < check.length; j++) {
            if (j!=check[j]) {
                return false;
            }
        }
    } catch (Exception e) {
        e.printStackTrace();
        //默认符合幻方规则，任意数组越界等错误都认为是不合格的数据
        return false;
    }
    return true;
}

下面开讲n(>=3)阶幻方的构造及实现

奇数阶幻方

拉-卢贝尔 算法

这个算法又称“阶梯法”。算法如下：

  1. 将1置于第一行中间。
  2. 将下一个数字置于当前数字的右上角。如果已经处于方阵的边界，则放在方阵的对边（如图1中的2和4）。
  3. 若出现下面两种情况，则将下一个数字放于当前数字的下方：

①当前位置的右上角已经有一个数字（如图2中的6和11）。

②当前位置已经是方阵的右上方（如图2中的16）。

  1. 结束，如下图3：

Java实现：

/**
 * k=*n+1
 * 拉-卢贝尔算法
 * 阶梯法
 */public static int[][] getSquarek1LenF1(int k) throws Exception{
    int[][] res = new int[k][k];
    int x =;
    int y = k/;
    int total = k*k;
    for (int i =; i <= total; i++) {
        res[x][y] = i;
        int m = (x-+k)%k;
        int n = (y+)%k;
        if (res[m][n]>) {
            x = (x+)%k;
        }else{
            x= m;
            y= n;
        }
    }
    return res;
}

菱形算法

另一种由康韦（J.H.Conway）建立的算法被称为“菱形算法”，步骤如下（以5×5为例）：

  1. 从左边中间开始，将奇数在方阵内填成一个菱形。
  2. 将方阵分成5条对角线，每条对角线上有5个方格。如果图1所示。
  3. 从第一条对角线开始将偶数填入剩余的空格内，图2中填满了前两条对角线。
  4. 结束，如图3。

再给一个7阶的构造填数过程，具体规则大家自己揣摩

Java实现：

/**
 * 菱形算法
 * k=*n+1
 */public static int[][] getSquarek1LenF2(int k) throws Exception{
    int[][] res = new int[k][k];
    //初始化奇数空间
    int n = k/;
    //奇数起点坐标
    int baseX = n,baseY =;
    //起点走向，true向右 false向下
    boolean type = true;
    //奇数计数
    int count =;
    //当前奇数坐标
    int x = baseX;
    int y = baseY;
    while(true){
        res[x][y] = count;
        count = count+;
        x--;y++;
        if (y>=x-n && y<=x+n) {
        }else{
            if (type) {
                baseY++;
            }else{
                baseX++;
            }
            type = !type;
            if (baseX==k- && baseY==n+1) {
 break ;
            }
            x = baseX;
            y = baseY;
        }
    }
    //偶数起点坐标
    int baseP = -;
    int baseQ = n+;
    //起点走向，true向右 false向下
    type = false;
    //偶数计数
    count =;
    //当前奇数坐标
    int p = baseP;
    int q = baseQ;
    while(true){
        p = (p+k)%k;
        q = (q+k)%k;
        res[p][q] = count;
        count = count+;
        p = (p-+k)%k;
        q = (q+)%k;
        if (res[p][q]!=) {
            if (type) {
                baseQ++;
            }else{
                baseP++;
            }
            type = !type;
            if (baseP==n && baseQ==k) {
                break;
            }
            p = baseP;
            q = baseQ;
        }
    }
    return res;
}

杨辉法

九子斜排 上下对易 左右相更 四维挺出 戴九履一 左三右七 二四为肩 六八为足

举个例子：9个数斜着排，上下的两个数1,9，左右的两个数3,7互相换一下，四个角上的2,4,6,8就移到那四个角上去，这样就填好了一个三阶幻方了.

再给一个7阶的构造填数过程，具体规则大家自己揣摩

Java实现：

/**
 * 九子斜排 上下对易 左右相更 四维挺出 戴九履一 左三右七 二四为肩 六八为足
 * k=*n+1
 */public static int[][] getSquarek1LenF3(int k) throws Exception{
    int[][] res = new int[k][k];
    //初始构造一个菱形空间
    int[][] dia = new int[*k-1][2*k-1];
    //把到k*k个数填入菱形空间
    for (int i =; i <= k*k; i++) {
        //计算i在菱形空间的坐标
        //批次
        int p = (i+(k-))/k;
        //偏移量
        int q = i%k==?k:i%k;
        q--;
        dia[p-+q][k-p+q] = i;
    }
    //填充中心
    int m = (k-)/2;
    for (int i = m; i <m+k ; i++) {
        for (int j = m; j < m+k; j++) {
            if (dia[i][j]==) {
                if (i<j) {
                    if(i+j<*k-1){
                        dia[i][j] = dia[i+k][j];
                    }else{
                        dia[i][j] = dia[i][j-k];
                    }
                }else{
                    if (i+j<*k-1) {
                        dia[i][j] = dia[i][j+k];
                    }else{
                        dia[i][j] = dia[i-k][j];
                    }
                }
            }
            //往结果集赋值
            res[i-m][j-m] = dia[i][j];
        }
    }
    return res;
}

单偶数阶幻方

侓克斯算法

这个算法也是由康韦给出的。思想是将方阵分成多个2×2的小方阵，小方阵按照位置分成L、U、X三种类型。然后在大体上按照卢-拉贝尔算法来走，在每个小方阵中根据小方阵的类型来填数。具体算法如下：

  1. 将方阵分成(2i+1)个(2×2)的小方阵，小方阵的分类这样确定：前i+1行是L类型，后面一行是U类型，最后的i-1行是X类型，然后交换第i+1行和第i+2行中间小方阵的类型。对于10×10的方阵如图1。
  2. L、U、X的填法如图2。
  3. 最终结果如图3。

Java实现：

/**
 * k=*n+2
 * 侓克斯算法
 * 
 * L: 1 U: 1 4 X: 1 4
 * 3 2 3 3 2
 * 
 * 前i+行是L类型，后面一行是U类型，最后的i-1行是X类型，然后交换第i+1行和第i+2行中间小方阵的类型
 */public static int[][] getSquarek2LenF1(int k) throws Exception{
    int[][] res = new int[k][k];
    int x =;
    int y = k/-1;
    int total = k*k/;
    for (int i =; i <= total; i++) {
        //定型
        //:L 0:U -1:X
        int type =;
        if ((x== k/+1 && y!=k/2-1) || (x==k/2-1 && y==k/2-1)) {
            type =;
        }
        if (x>= k/+3) {
            type = -;
        }
        //填充
        switch (type) {
            case:
            res[x][y] =*i;
            res[x][y+] = 4*i-3;
            res[x+][y] = 4*i-2;
            res[x+][y+1] = 4*i-1;
            break;
            case:
            res[x][y] =*i-3;
            res[x][y+] = 4*i;
            res[x+][y] = 4*i-2;
            res[x+][y+1] = 4*i-1;
            break;
            default:
            res[x][y] =*i-3;
            res[x][y+] = 4*i;
            res[x+][y] = 4*i-1;
            res[x+][y+1] = 4*i-2;
            break;
        }
        //定位
        int m = (x-+k)%k;
        int n = (y+)%k;
        if (res[m][n]>) {
            x = (x+)%k;
        }else{
            x= m;
            y= n;
        }
    }
 return res;
}

加法算法

将一个幻方加上另外一个幻方所得的和仍然具有幻方的特性，只是可能会有重复项，这是幻方的加法特性。下面的方法就是根据这个特性设计的，首先建立两个方阵A、B，具有幻方的特性（横、纵、斜和相同），然后让A加上B的i倍，就得到一个幻方。假如我们要作一个4i+2阶幻方（此处以14为例）。具体算法如下：

先作一个14（4i+2）阶的方阵A，这个方阵分成4个7（2i+1）阶小方阵，每个小方阵是一个奇数阶的幻方，奇数阶幻方构造方法已经有了。如图1。

  1. 先作一个14（4i+2）阶的方阵A，这个方阵分成4个7（2i+1）阶小方阵，每个小方阵是一个奇数阶的幻方，奇数阶幻方构造方法已经有了。如图1。
  2. 再作一个14（4i+2）阶的方阵B，这个方阵只由0、1、2、3构成，具体作法如下：

①第一列：3（i）个3,4（i+1）个0,5（i+2）个2,2（i-1）个1

②前7（2i+1）列与都与第一列相同，只有第4（i+1）列例外，该列第一个3和第一 个0交换位置。

③后7（2i+1）列与前7（2i+1）列相同，不过3和0交换，1和2交换。

④结果如图2。

  1. 构造幻方C=A+i2B。如图3,C即所求。

Java实现：

/**
 * 加法算法
 * k=*n+2
 */public static int[][] getSquarek2LenF2(int k) throws Exception{
    int[][] res = new int[k][k];
    //幻方A初始化
    int[][] sA = new int[k][k];
    int[][] temp = getSquarek1LenF1(k/2);
    for (int i =; i < k; i++) {
        for (int j =; j < k; j++) {
            sA[i][j] = temp[i%(k/)][j%(k/2)];
        }
    }
    //幻方B初始化
    int[][] sB = new int[k][k];
    int n = (k-)/4;
    for (int i =; i < k; i++) {
        for (int j =; j < k; j++) {
            if (i<k/ && j<n || i>=k/2 && j>=n && j<k/2) {
                sB[i][j]=;
            }
            if(i<k/ && j>=k/2 && j<3*n+3 || i>=k/2 && j>=3*n+3){
                sB[i][j]=;
            }
            if (i<k/ && j>=3*n+3 || i>=k/2 && j>=k/2 && j<3*n+3) {
                sB[i][j]=;
            }
        }
    }
    sB[n][] = 0;
    sB[n][n] =;
    sB[*n+1][0] = 3;
    sB[*n+1][n] = 0;
    //幻方A和幻方B相加
    //RES = A + B*k*k/
    for (int i =; i < k; i++) {
        for (int j =; j < k; j++) {
            res[i][j] = sA[i][j]+sB[i][j]*k*k/;
        }
    }
    return res;
}

双偶数阶幻方

分割算法

  1. 将方阵分成16个小方阵，如图1。
  2. 先在A、C、E、G、I方阵中填入数字，其他方阵跳过,如图2。
  3. 再逆序（从右下往左上）赶往余下的数字,如图3。
  4. 结束，如图3

下面是一个8次的方阵：

Java实现：
/**
 * k=*n
 * 分割算法
 */public static int[][] getSquarekLenF1(int k) throws Exception{
    int[][] res = new int[k][k];
    //分割数据临时数组
    int[] temp = new int[k*k/];
    int index =;
    //预填充
    for (int i =; i < k; i++) {
        for (int j =; j < k; j++) {
            //符合分割条件
            int m = i%;
            int n = j%;
            if (m!=n && m+n!=) {
                temp[index++] = i*k+j+;
                res[i][j]=;
            }else{
                res[i][j] = i*k+j+;
            }
        }
    }
    //分割出的数据排序
    Arrays.sort(temp);
    int tempIndex = temp.length-;
    //再填充
    for (int i =; i < k; i++) {
        for (int j =; j < k; j++) {
            if (res[i][j]==) {
                res[i][j] = temp[tempIndex--];
            }
        }
    }
    return res;
}

对角线算法

  1. 将数字顺序填入方阵内,如图1。
  2. 将方阵分成四个相同大小的方阵。并找出每个小方阵的对角线，如图1阴影部分。
  3. 将阴影部分旋转180度，如图2。

Java实现：

/**
 * 对角线算法
 * k=*n
 */public static int[][] getSquarekLenF2(int k) throws Exception{
    int[][] res = new int[k][k];
    for (int i =; i < k; i++) {
        for (int j =; j < k; j++) {
            //坐标i,j是否处在对角线规则内
            int m = i%;
            int n = j%;
            if (m==n || m+n==) {
                res[i][j] = (k--i)*k+(k-1-j)+1;
            }else{
                res[i][j] = i*k+j+;
            }
        }
    }
    return res;
}

Spring Boot 打包插件，真是太有用了
上一篇
浅学Spring启用Log4j日志框架
下一篇