六角填数

标题：六角填数


    如图所示六角形中，填入1~12的数字。


    使得每条直线上的数字之和都相同。


    图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？

请通过浏览器提交答案，不要填写多余的内容。

答案：10

1、深搜

#include<stdio.h>
int a[13] = {0}; // 代表那12个圈中的数 
int b[13] = {0}; // 代表1-12的数字是否已被使用 

void judge(){
	int num[7];
	int i;
	num[1] = a[1] + a[3] + a[6] + a[8];
	num[2] = a[1] + a[4] + a[7] + a[11];
	num[3] = a[2] + a[3] + a[4] + a[5];
	num[4] = a[2] + a[6] + a[9] + a[12];
	num[5] = a[5] + a[7] + a[10] + a[12];
	num[6] = a[8] + a[9] + a[10] + a[11];
	for(i = 2; i < 7; i++){
		if(num[i] != num[i - 1])
			return;
	}
	printf("%d", a[6]);
}

void dfs(int m){
	int i;
	if(m == 1 || m == 2 || m == 12){
		dfs(m + 1);
		return;
	}
		
	if(m == 13)
		judge();
	
	for(i = 1; i <= 12; i++){
		if(b[i] == 0){
			b[i] = 1;
			a[m] = i;
			dfs(m + 1);
			b[i] = 0;
		}
	}
	
}

int main(){
	int i, j;
	a[1] = 1, a[2] = 8, a[12] = 3; // 第一、二、十二个圈中都有数
	b[1] = 1, b[3] = 1, b[8] = 1; // 1、3、8都已被使用
	dfs(1);
	return 0; 
}

2、全排列：next_permutation

#include<stdio.h>
#include<algorithm>
int main() {
	int num[7];
	int a[13] = {0,1,8,2,4,5,6,7,9,10,11,12,3};
	do {
		num[1] = a[1] + a[3] + a[6] + a[8];
		num[2] = a[1] + a[4] + a[7] + a[11];
		num[3] = a[2] + a[3] + a[4] + a[5];
		num[4] = a[2] + a[6] + a[9] + a[12];
		num[5] = a[5] + a[7] + a[10] + a[12];
		num[6] = a[8] + a[9] + a[10] + a[11];
		
		if(num[1]==num[2] && num[2]==num[3] && num[3]==num[4] && num[4]==num[5] && num[5]==num[6])
			printf("%d\n", a[6]);
	} while(std::next_permutation(a+3, a+12)); // a 数组中前三个（0,1,8）和最后一个（3）不参与排列 
	return 0;
}