反幻方

我国古籍很早就记载着

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

等都算作同一种情况。

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

答案：

旋转加镜像一共八种情况重复。

代码：

import java.util.Scanner;

public class Main {
    private static Scanner sc = new Scanner(System.in);
    private static boolean[] vis = new boolean[10];
    private static int c = 0;
    private static int [] s = new int[10];
    private static boolean check() {
        boolean [] v = new boolean[30];
        int d;
        for(int i = 0;i < 3;i ++) {
            d = s[i] + s[i + 3] + s[i + 6];
            if(v[d]) return false;
            v[d] = true;
            d = s[i * 3] + s[i * 3 + 1] + s[i * 3 + 2];
            if(v[d]) return false;
            v[d] = true;
        }
        d = s[0] + s[4] + s[8];
        if(v[d]) return false;
        v[d] = true;
        d = s[2] + s[4] + s[6];
        if(v[d]) return false;
        return true;
    }
    private static void dfs(int k) {
        if(k >= 9) {
            if(check()) c ++;
            return;
        }
        for(int i = 1;i <= 9;i ++) {
            if(vis[i]) continue;
            vis[i] = true;
            s[k] = i;
            dfs(k + 1);
            vis[i] = false;
        }
    }
    public static void main(String[] args) {
        dfs(0);
        System.out.println(c / 8);
    }
}

#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
int ans[9];
int c;
bool vis[10],val[25];
void dfs(int k) {
    int d = 0,e = 0,f = 0;
    if(k && k % 3 == 0) {
        d = ans[k - 3] + ans[k - 2] + ans[k - 1];
        if(val[d]) return;
        val[d] = true;
    }
    if(k > 6) {
        e = ans[k - 1] + ans[k - 4] + ans[k - 7];
        if(val[e]) {
            val[d] = false;
            return;
        }
        val[e] = true;
    }
    if(k == 7) {
        f = ans[6] + ans[4] + ans[2];
        if(val[f]) {
            val[d] = val[e] = false;
            return;
        }
        val[f] = true;
    }
    if(k == 9) {
        if(!val[ans[0] + ans[4] + ans[8]]) c ++;
        val[d] = val[e] = val[f] = false;
        return;
    }
    for(int i = 1;i <= 9;i ++) {
        if(vis[i]) continue;
        vis[i] = true;
        ans[k] = i;
        dfs(k + 1);
        vis[i] = false;
    }
    val[d] = val[e] = val[f] = false;
}
int main() {
    dfs(0);
    printf("%d",c / 8);
}