蓝桥杯决赛--反幻方

题目描述

我国古籍很早就记载着

2 9 4
7 5 3
6 1 8

这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。

下面考虑一个相反的问题。
可不可以用 1~9 的数字填入九宫格。
使得：每行每列每个对角线上的数字和都互不相等呢？

这应该能做到。
比如：
9 1 2
8 4 3
7 5 6

你的任务是搜索所有的三阶反幻方。并统计出一共有多少种。
旋转或镜像算同一种。

比如：
9 1 2
8 4 3
7 5 6

7 8 9
5 4 1
6 3 2

2 1 9
3 4 8
6 5 7

等都算作同一种情况。

请提交三阶反幻方一共多少种。这是一个整数，不要填写任何多余内容。

解题思想

/* 因为本题是个填空题，所以就不考察时间复杂度了，只要能写出来就ok了 那么说下思路，1--9全排列一下（全排列这里指排列+组合） 然后验证一下都不相等就可以了。 */

代码

//答案是3120
import java.util.Scanner;
public class Main{
    static int[] arr= {1,2,3,4,5,6,7,8,9}; // 枚举数组
    static int[] vis = new int[arr.length]; //标记数组
    static int[] m = new int[arr.length]; //排列组合 数组
    static int count = 0;
    public static void main(String[] args){
        dfs(0);
        //初8是应为，旋转4个+镜像2个
        System.out.println(count/8);
    }

    public static void dfs(int k){

        if(k==arr.length){
        //下面是检测是否每个位置都不相等
            boolean flag = true;
            int row1 = m[0]+m[1]+m[2];
            int row2 = m[3]+m[4]+m[5];
            int row3 = m[6]+m[7]+m[8];
            int col1 = m[0]+m[3]+m[6];
            int col2 = m[1]+m[4]+m[7];
            int col3 = m[2]+m[5]+m[8];
            int xie1 = m[0]+m[4]+m[8];
            int xie2 = m[2]+m[4]+m[6];
            int[] p = {row1,row2,row3,col1,col2,col3,xie1,xie2};
            for(int i=0; i<p.length; ++i)
                for(int j=i+1; j<p.length; ++j){
                    if(p[i]==p[j]){
                        flag = false;
                        break;
                    }
                    if(!flag)
                        break;
                }
            if(flag)
                count++;
            return;
        }
        //这里是试探-回溯的过程，全排列
        for(int i=0; i<9; ++i){
            if(vis[i] == 0){
                vis[i] = 1;
                m[k] = arr[i];
                dfs(k+1);
                vis[i] = 0;
            }
        }
    }
}