题目：四阶幻方
把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时的所有方案数字，不要填写任何多余内容或说明文字。
答案：
public class Main
{
static int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 };
static int count = 0;
// 穷举法+DFS
public static void main(String[] args)
{
dfs(1);
System.out.println(count);
}
// 因为dfs()的结构为先判断，再操作，再进入下一层，再还原。
// 所以当k == 1时，操作了第一个位置，当 k== 2时，才能判断2个元素。
// 要判断16个元素，就要 k == 16,也就是arr.length。
public static void dfs(int k)
{
// 当 k == arr[]的长度的时候，就意味着16个数字都填好了。
if (k == arr.length)
{
// 最后一行 && 最后一列
if (arr[12] + arr[13] + arr[14] + arr[15] == 34 && arr[15] + arr[11] + arr[7] + arr[3] == 34)// 判断最后一行
// 右对角线线 && 左对角线 是否等于34
if (arr[12] + arr[9] + arr[6] + arr[3] == 34 && arr[0] + arr[5] + arr[10] + arr[15] == 34)// 之后判断 每列
count++;
return;
}
// k / 4 != 0 && k % 4 == 0 这样的条件就可以限定 k 为4的倍数
// 这里有一个思想：当有5个元素的时候(我放了4个)，我就比较0/1/2/3这四个；当有9个元素的时候(我放了8个)，我就比较 4/5/6/7这四个。
// 这个if语句是用来判断每一行的，在DFS的时候，一边深入一边检测每一行。
if (k / 4 != 0 && k % 4 == 0)
{// 每次改变顺序够4个 就判断是否等于34
int n = k / 4;
if (arr[n * 4 - 4] + arr[n * 4 - 3] + arr[n * 4 - 2] + arr[n * 4 - 1] != 34)
return;
}
// (k - 1) / 4 == 3 用这样的条件，就能捕捉到 13/14/15/16 这几个数字
// 这个if语句是用来判断每一列的，在DFS的时候，一边深入一边比较每一列。
if ((k - 1) / 4 == 3)
{// 判断每列是否符合 因为到第四行的时候才能判断列 当到达第四行第一个时还没进行交换 所以当遍历到第二个时
// 再判断他前面的位置是否到了第四行，然后每个位置除四的余数正好是它所在第几个的位置
int n = (k - 1) % 4;
if (arr[0 + n] + arr[4 + n] + arr[8 + n] + arr[12 + n] != 34)
return;
}
for (int i = k; i < arr.length; i++)
{
// 把arr[k]与arr[i]的值互换
int t = arr[k];
arr[k] = arr[i];
arr[i] = t;
//
dfs(k + 1);
// 把arr[i]与arr[k]的值互换
t = arr[k];
arr[k] = arr[i];
arr[i] = t;
}
}
}