标题：六角幻方

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

    * * *
   * * * *
  * * * * *
   * * * * 
    * * *

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

    再给点线索吧！我们预先填好了2个数字，第一行的头两个数字是：15 13，参见图【p1.png】，黄色一行为所求。

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

    这是一行用空格分开的整数，请通过浏览器提交答案，不要填写任何多余的内容（比如说明性的文字等）

解题报告：

  好久没写搜索了，，当个练习。

不难发现每一行的值的和应该是38，所以我们已经有了三个已知数字了。

根据对称性把这三个数放在每一行的开始，相当于有了三个已知行的行首，然后按行dfs，同时判断是否凑够了38，如果超了38那就直接return就行，这一点可以用附初始值为比较大的值（这里用了100000）来实现。如果还没填满这一行但是和已经大于38了  或者  都填满了并且还不是38，那就return。这应该是最优秀的剪枝了，是每一步都会有剪枝。当然如果不这样剪枝，而是直接： 每一行都填满了再判断是否等于38，也可以。

最终答案：

10 12 16
13 4 2 19
15 8 5 7 3
14 6 1 17
9 11 18

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int a[55][55],all[55] = {0,10,13,15,0,0};
int up[55] = {0,3,4,5,4,3};
bool vis[55],ok[55][55];
bool cc() {
	if(a[1][2]+a[2][2]+a[3][2]+a[4][1]!=38) return 0;
	if(a[1][3]+a[2][3]+a[3][3]+a[4][2]+a[5][1]!=38) return 0;
	if(a[2][4]+a[3][4]+a[4][3]+a[5][2]!=38) return 0;
	if(a[3][5]+a[4][4]+a[5][3]!=38) return 0;
	
	if(a[1][3]+a[2][4]+a[3][5]!=38) return 0;
	if(a[1][2]+a[2][3]+a[3][4]+a[4][4]!=38) return 0;
	if(a[1][1]+a[2][2]+a[3][3]+a[4][3]+a[5][3]!=38) return 0;
	if(a[2][1]+a[3][2]+a[4][2]+a[5][2]!=38) return 0;
	if(a[3][1]+a[4][1]+a[5][1]!=38) return 0;
	return 1;
}
bool check() {
	if(a[1][2]+a[2][2]+a[3][2]+a[4][1]!=38 && a[1][2]+a[2][2]+a[3][2]+a[4][1]<100000) return 0;
	if(a[1][3]+a[2][3]+a[3][3]+a[4][2]+a[5][1]!=38 && a[1][3]+a[2][3]+a[3][3]+a[4][2]+a[5][1]<100000) return 0;
	if(a[2][4]+a[3][4]+a[4][3]+a[5][2]!=38 && a[2][4]+a[3][4]+a[4][3]+a[5][2]<100000) return 0;
	if(a[3][5]+a[4][4]+a[5][3]!=38 && a[3][5]+a[4][2]+a[5][3]<100000) return 0;
	
	if(a[1][3]+a[2][4]+a[3][5]!=38 && a[1][3]+a[2][4]+a[3][5]<100000) return 0;
	if(a[1][2]+a[2][3]+a[3][4]+a[4][4]!=38 && a[1][2]+a[2][3]+a[3][4]+a[4][4]<100000) return 0;
	if(a[1][1]+a[2][2]+a[3][3]+a[4][3]+a[5][3]!=38 && a[1][1]+a[2][2]+a[3][3]+a[4][3]+a[5][3]<100000) return 0;
	if(a[2][1]+a[3][2]+a[4][2]+a[5][2]!=38 && a[2][1]+a[3][2]+a[4][2]+a[5][2]<100000) return 0;
	if(a[3][1]+a[4][1]+a[5][1]!=38 && a[3][1]+a[4][1]+a[5][1]<100000) return 0;	
	return 1;
}
void dfs(int x,int y) {
	if(x == 6) {
		if(cc() == 0) return;
		for(int i = 1; i<=5; i++) {
			for(int j = 1; j<=up[i]; j++) {
				printf("%d ",a[i][j]);
			}
			printf("\n");
		}
		return;			
	}
	if(check() == 0) return;
	if(ok[x][y]) {
		dfs(x,y+1);return;
	}
	for(int i = 1; i<=19; i++) {
		if(vis[i]) continue;
		if(all[x] + i > 38) continue;
		if(y == up[x]) {
			if(all[x] + i != 38) continue;
			else {
				all[x] += i;
				vis[i] = 1;
				a[x][y] = i;
				dfs(x+1,1);
				a[x][y] = 100000;
				all[x] -= i;
				vis[i] = 0;
				return;
			}
		}
		vis[i] = 1;
		all[x] += i;
		a[x][y] = i;
		dfs(x,y+1);
		a[x][y] = 100000;
		vis[i] = 0;
		all[x] -= i;
	}	
}
int main()
{
	for(int i = 1; i<=5; i++) {
		for(int j = 1; j<=5; j++) a[i][j] = 100000;
	}
	a[1][1]=10;a[2][1]=13;a[3][1]=15;
	ok[1][1]=1;ok[2][1]=1;ok[3][1]=1;
	vis[10]=1;vis[13]=1;vis[15]=1;
	dfs(1,1);
	return 0 ;
}
//19:00-19:20

/*
10 12 16
13 4 2 19
15 8 5 7 3
14 6 1 17
9 11 18

*/