六角填数（全排列-抓取法）

1. 问题描述：

如图所示六角形中，填入1~12的数字。
使得每条直线上的数字之和都相同。
图中，已经替你填好了3个数字，请你计算星号位置所代表的数字是多少？

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

2. 思路分析：

① 对于这种填数字的我们首先要有一种全局的思维，因为这样的问题经典的解法是使用全排列去求解，套路是先生成所有的全排列然后在出口的时候使用check函数进行判断，因为数据规模还不是特别大，所以是可以使用全排列的递归求解出来的

② 对于题目中的数字我们是将其转化为一维数组来做的，所以可以将1-12的数字放入到一个整型数组中，这里使用抓取法去生成去全排列，即先声明一个标记元素是否被访问过的整型数组来判断当前当前是否已经被访问过，然后声明一个放结果的整型数组用来存在在递归求解的过程中生成的排列

③ 对图中的所有格子进行标号，分别从1-12从上到下进行标记，标记的目的是为了在出口的时候能够对生成的排列来判断六条直线的和是否满足题目的要求，这里可以使用一个check函数进行判断，判断成功之后那么我们需要再一次判断第一个，第二个，第十二个元素是否是1,8,3，如果是1,8,3那么直接输出到控制台上

④ 可以发现输出来的结果只有一个那么我们需要手工验证一下看结果是否正确

⑤ 在写传进数组下标和判断条件的时候要细心一点因为这里存在着多个的数组，容易写错

3. 具体的代码如下：

public class Main {static int count;static int visit[] = new int[13];static int res[] = new int[13];public static void main(String[] args) {int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};f(arr, 0);System.out.println(count);}private static void f(int[] arr, int k) {if(k == 12){if(check(res)){//进行筛选//注意这里容易写错if(res[1] == 1 && res[2] == 8 && res[12] == 3){for(int i = 1; i <= 12; i++){System.out.print(res[i] + " ");}System.out.println();}count++;}return;}for(int i = 1; i <= 12; i++){if(visit[i] == 0){visit[i] = 1;//注意这里容易出现错误res[k + 1] = arr[i - 1];f(arr, k + 1);//回溯visit[i] = 0;res[k + 1] = 0;}}}private static boolean check(int res[]) {//依次判断所有直线的结果是否是一样的int sum1 = res[1] + res[3] + res[6] + res[8];int sum2 = res[1] + res[4] + res[7] + res[11];int sum3 = res[8] + res[9] + res[10] + res[11];int sum4 = res[2] + res[3] + res[4] + res[5];int sum5 = res[2] + res[6] + res[9] + res[12];int sum6 = res[5] + res[7] + res[10] + res[12];if(sum2 != sum1) return false;if(sum3 != sum2) return false;if(sum4 != sum3) return false;if(sum5 != sum4) return false;if(sum6 != sum5) return false;return true;}
}