【回溯】B027_LQ_六角幻方 四阶幻方 九宫幻方 反幻方 魔方状态 纸牌三角形（恶心的剪枝）

一、六角幻方

把 1、2、3 … 19 共 19 个整数排列成六角形状，如下：

要求每个直线上的数字之和必须相等，共有 15 条 直线哦！

再给点线索吧！我们预先填好了 2 个数字，第一行的头两个数字是：15、13，如图。

请你填写出黄色一行的 5 个数字。数字间用空格分开

方法一：深搜+剪枝

思路

真的恶心,

#include<bits/stdc++.h>
using namespace std;
int a[20]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
int A[19], vis[19];
void dfs(int i) {if (i==7 && 28+A[2] != A[3]+A[4]+A[5]+A[6]) return;if (i==8 && 28+A[2] != A[0]+A[3]+A[7]) return;if (i==12 && (28+A[2] != A[7]+A[8]+A[9]+A[10]+A[11] || 28+A[2] != A[2]+A[6]+A[11])) return;if (i==13 && 28+A[2] != A[1]+A[4]+A[8]+A[12]) return;if (i==16 && (28+A[2] != A[12]+A[13]+A[14]+A[15] || 28+A[2] != A[5]+A[10]+A[15])) return;if (i==17 && (28+A[2] != A[2]+A[5]+A[9]+A[13]+A[16] || 28+A[2]!=A[7]+A[12]+A[16])) return;if (i==18 && (28+A[2] != A[6]+A[10]+A[14]+A[17] || 28+A[2] != A[3]+A[8]+A[13]+A[17])) return;if (i==19 && 28+A[2] == A[16]+A[17]+A[18]) {for (int k=7; k<=11; k++) printf("%d ", A[k]);return;}for (int j=1; j<20; j++) {if (vis[j]) continue;vis[j]=1;A[i]=a[j-1];dfs(i+1);vis[j]=0;}
}
int main() {memset(vis, 0, sizeof vis);A[0]=15, A[1]=13; vis[13]=vis[15]=1;dfs(2);return 0;
}

二、四阶幻方

把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
就可以算为两种不同的方案

代码类似，需要恶心的剪枝…

#include<bits/stdc++.h>
using namespace std;
int ans, A[17], vis[17];void dfs(int i) {if (i==8 && A[0]+A[1]+A[2]+A[3] != A[4]+A[5]+A[6]+A[7]) return;if (i==12 && A[4]+A[5]+A[6]+A[7] != A[8]+A[9]+A[10]+A[11]) return;if (i==13 && (A[8]+A[9]+A[10]+A[11] != A[0]+A[4]+A[8]+A[12] || A[8]+A[9]+A[10]+A[11] != A[3]+A[6]+A[9]+A[12])) return;if (i==14 && A[8]+A[9]+A[10]+A[11] != A[1]+A[5]+A[9]+A[13]) return;if (i==15 && A[8]+A[9]+A[10]+A[11] != A[2]+A[6]+A[10]+A[14]) return;if (i==16) {int s1=A[8]+A[9]+A[10]+A[11], s2=A[12]+A[13]+A[14]+A[15], s3=A[3]+A[7]+A[11]+A[15], s4=A[0]+A[5]+A[10]+A[15];if (s1!=s2 || s1!=s3 || s1!=s4) return;ans++;}for (int next=1; next<17; next++) if (!vis[next]) {vis[next]=1, A[i]=next;dfs(i+1);vis[next]=0;}
}
int main() {std::ios::sync_with_stdio(false);vis[1]=1;A[0]=1;dfs(1);cout << ans;return 0;
}

三、九宫幻方

小明最近在教邻居家的小朋友小学奥数，而最近正好讲述到了三阶幻方这个部分，三阶幻方指的是将1~9不重复的填入一个3*3的矩阵当中，使得每一行、每一列和每一条对角线的和都是相同的。

三阶幻方又被称作九宫格，在小学奥数里有一句非常有名的口诀：“二四为肩，六八为足，左三右七，戴九履一，五居其中”，通过这样的一句口诀就能够非常完美的构造出一个九宫格来。

4 9 2
3 5 7
8 1 6

有意思的是，所有的三阶幻方，都可以通过这样一个九宫格进行若干镜像和旋转操作之后得到。现在小明准备将一个三阶幻方（不一定是上图中的那个）中的一些数抹掉，交给邻居家的小朋友来进行还原，并且希望她能够判断出究竟是不是只有一个解。

而你呢，也被小明交付了同样的任务，但是不同的是，你需要写一个程序~

输入
输入仅包含单组测试数据。
每组测试数据为一个3*3的矩阵，其中为0的部分表示被小明抹去的部分。
对于100%的数据，满足给出的矩阵至少能还原出一组可行的三阶幻方。
输出
如果仅能还原出一组可行的三阶幻方，则将其输出，否则输出“Too Many”（不包含引号）

样例输入
0 7 2
0 5 0
0 3 0
样例输出
6 7 2
1 5 9
8 3 4

#include<bits/stdc++.h>
using namespace std;int ans, A[10], put[10], bk[10], B[10];
void dfs(int i) {if (i==7 && A[1]+A[2]+A[3]!=A[4]+A[5]+A[6]) return;if (i==8 && (A[4]+A[5]+A[6]!=A[1]+A[4]+A[7] || A[4]+A[5]+A[6]!=A[3]+A[5]+A[7])) return;if (i==9 && A[2]+A[5]+A[8]!=A[4]+A[5]+A[6]) return;if (i==10 && A[7]+A[8]+A[9]==A[2]+A[5]+A[8] && A[7]+A[8]+A[9]==A[1]+A[5]+A[9]) {ans++;for (int j=1; j<10; j++) B[j]=A[j];return;}if (put[i]) {dfs(i+1); } else {for (int j=1; j<10; j++) if (!bk[j]) {bk[j]=1, A[i]=j;dfs(i+1);bk[j]=0;}}
}
int main() {std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);for (int i=1; i<=9; i++) {cin>>A[i];if (A[i]>0) put[i]=true;}dfs(1);if (ans==1) {for (int i=1; i<=9; i++) {cout << B[i] << ' ';if (i%3==0) cout << '\n';}} else {cout << "Too Many";}return 0;
}

四、反幻方

我国古籍很早就记载着

2 9 4 
7 5 3 
6 1 8 

这是一个三阶幻方。每行每列以及对角线上的数字相加都相等。
下面考虑一个相反的问题。
可不可以用 1~9 的数字填入九宫格，使得：每行每列每个对角线上的数字和都互不相等呢？
这应该能做到。
比如：

9 1 2 
8 4 3 
7 5 6 

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

9 1 2     7 8 9     2 1 9 
8 4 3     5 4 1     3 4 8 
7 5 6     6 3 2     6 5 7 

3120

{//答案是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])return;}count++;return;
}

五、魔方状态

二阶魔方就是只有2层的魔方，只由8个小块组成。如图所示。

小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：
前面：橙色、右面：绿色、上面：黄色、左面：绿色、下面：橙色、后面：黄色
请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。
如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。

六、纸牌三角形

A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。
下图就是一种排法这样的排法可能会有很多。
如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？

对结果除以 3 再除以 2