java螺旋填數三角形_第八屆藍橋杯Java B——紙牌三角形

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 set = new HashSet();

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];

}

}