问题提出：
上述问题就是典型的全排列问题！！
一、回溯法
回溯：就是类似枚举的搜索尝试过程。在搜索过程中寻找问题的解。当发现不满足求解的条件时，就回溯返回，尝试别的路径。
全排列可以使用试探的方法列举所有的可能性。一个长度为n的序列，所有排列组合：n！
1.从集合中选取一个元素(n种情况)，并标记该元素已被使用
2. 在第一步的基础上递归到下一层，从剩余的n-1个元素中，按照第一步的方法找到一个元素，并标记(n-1)
3. 以此类推，所有元素都被标记，将元素存起来，去对比求解的情况
在解题前我们先给定数组在三角形上的对应下标：
代码实现：
public class 全排列_回溯法 { static int count = 0;// 记录总个数 static boolean[] bool = new boolean[10]; static int[] arr = new int[10];// 存放数据 public static void main(String[] args) { dfs(1); System.out.println(count / 6);//144 } public static void dfs(int step) { // 结束条件 if (step == 10) { if (arr[1] + arr[2] + arr[3] + arr[4] == arr[4] + arr[5] + arr[6] + arr[7] && arr[1] + arr[2] + arr[3] + arr[4] == arr[7] + arr[8] + arr[9] + arr[1]) { count++; } return; } for (int i = 1; i < 10; i++) { // 判断i位置上是否放置了数字 if (!bool[i]) { arr[step] = i; bool[i] = true; dfs(step + 1); bool[i] = false; } } } }
二、邻里交换法
邻里交换法：
回溯是试探性填充数据，给每个位置都试探性赋值
邻里交换，也是通过递归实现，但是是一种基于交换的思路
步骤：
1.将数组分为2个部分，暂时确定部分和未确定部分，刚开始都是未确定部分在未确定的部分中，让每一个数据都有机会和未确定部分中的第一位交换，然后第一位就变成暂时确定部分。
2. 以此类推：每个数据都和未确定部分中的第二位交换（第一位数据除外）...直到确定所有数据。
3. 将确定好的数据和条件对比，对比结束后，还原数据。
代码实现：
public class 全排列_邻里交换法 { static int count = 0; static int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; public static void main(String[] args) { f(arr, 0); System.out.println(count / 6);//144 } public static void f(int arr[], int step) { if (step == arr.length - 1) { if (arr[0] + arr[1] + arr[2] + arr[3] == arr[3] + arr[4] + arr[5] + arr[6] && arr[0] + arr[1] + arr[2] + arr[3] == arr[6] + arr[7] + arr[8] + arr[0]) { count++; } return; } for (int i = step; i < arr.length; i++) { // 交换 { int temp = arr[i]; arr[i] = arr[step]; arr[step] = temp; } f(arr, step + 1); // 还原数据 { int temp = arr[i]; arr[i] = arr[step]; arr[step] = temp; } } } }
三、暴力解法
public class 全排列_暴力解法 { static int count = 0; public static void main(String[] args) { for (int a = 1; a <= 9; a++) {// 1 for (int b = 1; b <= 9; b++) {// 2 for (int c = 1; c <= 9; c++) {// 3 for (int d = 1; d <= 9; d++) {// 4 for (int e = 1; e <= 9; e++) {// 5 for (int f = 1; f <= 9; f++) {// 6 for (int g = 1; g <= 9; g++) {// 7 for (int h = 1; h <= 9; h++) {// 8 for (int i = 1; i <= 9; i++) {// 9 // 不能重复 if (a == b || a == c || a == d || a == e || a == f || a == g || a == h || a == i || b == c || b == d || b == e || b == f || b == g || b == h || b == i || c == d || c == e || c == f || c == g || c == h || c == i || d == e || d == f || d == g || d == h || d == i || e == f || e == g || e == h || e == i || f == g || f == h || f == i || g == h || g == i || h == i) { continue; } if (a + b + c + d == d + e + f + g && a + b + c + d == g + h + i + a) { count++; } } } } } } } } } } System.out.println(count / 6);//144 } }
