六角填数之全排列

算法步骤

（1）为需要填充的所有点规定一个顺序，按照该顺序确定一个满足行和都相等的模型；
（2）将所有可以填充的数字进行全排列，也就是这些数字组合的所有可能(这里的全排列通过递归来实现，采用树形分解法)；
（3）将步骤(2)全排列结果依次带入步骤(1)，直到找到满足条件的组合。

实例以及代码

问题描述：在如图所示的六角形中，每一个圆圈都可以填入一个数字，现需要将整数1-12填入，使得填入后的每条直线的和都相等。问红色星号处填入的数字是多少？

实例代码

//未填入的数字
int data[9]={2,4,5,6,7,9,10,11,12};

//判断目前的填入方式是否满足条件
int judge(){
	int num[7],i;
	int a[13] = {0}; // 代表那12个圈中的数
	// 第一、二、十二个圈中都有数 
	a[1] = 1, a[2] = 8, a[12] = 3; 
	for(i=0;i<9;i++)
		a[i+3]=data[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 0;
	}
	return a[6];	
}

//对未填入数字进行全排列
void FullPermutation(int start,int end){
	int i,t;
	if(start==end)  //对每一个全排列进行验证
	{
		if(judge())
			printf("红色星号位置应填入:%d",judge());
	}
	else
	{
		for(i=start;i<=end;i++)
	    {
			t=data[i];
			data[i]=data[start];
			data[start]=t;
			FullPermutation(start+1,end);
			data[start]=data[i];
			data[i]=t;
	    }
	}
}

int main(){
    FullPermutation(0,8);
	return 0; 
}

运行结果