A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形(A按1计算)。要求每个边的和相等。
下图就是一种排法
这样的排法可能会有很多。
如果考虑旋转、镜像后相同的算同一种,一共有多少种不同的排法呢?
import java.util.HashSet; import java.util.Set; public class Main { static boolean[] book = new boolean[9]; static int[] arr = new int[9]; static int ans; static Set<String> set = new HashSet<String>(); public static void main(String[] args) { dfs(0); System.out.println(ans); } // 金字塔顶是arr[0],剩下的顺序按照顺时针排下来 static void dfs(int idx) { if (idx == 7 && check_7()) // 剪枝 return; else if (idx == 9) { if (check_9()) { StringBuilder a = new StringBuilder("").append(arr[0]).append(arr[1]).append(arr[2]).append(arr[3]); StringBuilder b = new StringBuilder("").append(arr[3]).append(arr[4]).append(arr[5]).append(arr[6]); StringBuilder c = new StringBuilder("").append(arr[6]).append(arr[7]).append(arr[8]).append(arr[0]); if (!set.contains(a + "" + b + c)) { set.add(a + "" + b + c); set.add(b + "" + c + a); set.add(c + "" + a + b); a.reverse();b.reverse();c.reverse(); set.add(c + "" + b + a); set.add(a + "" + c + b); set.add(b + "" + a + c); ans++; } } return; } for (int i = 1; i <= 9; i++) { if (!book[i - 1]) { book[i - 1] = true; arr[idx] = i; dfs(idx + 1); book[i - 1] = false; } } } static boolean check_9() { return arr[0] + arr[1] + arr[2] + arr[3] == arr[3] + arr[4] + arr[5] + arr[6] && arr[3] + arr[4] + arr[5] + arr[6] == arr[6] + arr[7] + arr[8] + arr[0]; } static boolean check_7() { return arr[0] + arr[1] + arr[2] != arr[4] + arr[5] + arr[6]; } }