java实现第六届蓝桥杯四阶幻方

四阶幻方

把1~16的数字填入4x4的方格中，使得行、列以

及两个对角线的和都相等，满足这样的特征时称

为：四阶幻方。

四阶幻方可能有很多方案。如果固定左上角为1

，请计算一共有多少种方案。

比如：

1 2 15 16

12 14 3 5

13 7 10 4

8 11 6 9

以及：

1 12 13 8

2 14 7 11

15 3 10 6

16 5 4 9

就可以算为两种不同的方案。

请提交左上角固定为1时的所有方案数字，不要

填写任何多余内容或说明文字。

答案：416

import java.util.ArrayList;

public class Main {

    public static boolean[] used = new boolean[17];

    public static ArrayList<String> list = new ArrayList<String>();

    public static int count = 0;

    public boolean check(int[] A, int step) {

        if(step >= 4)

            if(A[0] + A[1] + A[2] + A[3] != 34)

                return false;

        if(step >= 8)

            if(A[4] + A[5] + A[6] + A[7] != 34)

                return false;

        if(step >= 12)

            if(A[8] + A[9] + A[10] + A[11] != 34)

                return false;

        if(step >= 13)

            if(A[0] + A[4] + A[8] + A[12] != 34 || A[3] + A[6] + A[9] + A[12] != 34)

                return false;

        if(step >= 14)

            if(A[1] + A[5] + A[9] + A[13] != 34)

                return false;

        if(step >= 15)

            if(A[2] + A[6] + A[10] + A[14] != 34)

                return false;

        if(step >= 16)

            if(A[3] + A[7] + A[11] + A[15] != 34 || A[0] + A[5] + A[10] + A[15] != 34)

                return false;

        return true;

    }

    public void dfs(int[] A, int step) {

        if(check(A, step) == false)

            return;

        if(step == 16) {

            StringBuffer s = new StringBuffer("");

            for(int i = 0;i < A.length;i++)

                s.append(A[i]);

            if(!list.contains(s.toString())) {

                list.add(s.toString());

                count++;

            }

            return;

        }

        for(int i = 2;i <= 16;i++) {

            if(used[i] == false) {

                used[i] = true;

                A[step] = i;

                dfs(A, step + 1);

                used[i] = false;

            }

        }

    }

    public static void main(String[] args) {

        Main test = new Main();

        int[] A = new int[16];

        A[0] = 1;

        used[1] = true;

        test.dfs(A, 1);

        System.out.println(count);

    }

}

巴特西

java实现第六届蓝桥杯四阶幻方

最新文章

热门文章