### Tri-colouring a triangular grid题号：189 难度： 70 中英对照

Consider the following configuration of 64 triangles:

We wish to colour the interior of each triangle with one of three colours: red, green or blue, so that no two neighbouring triangles have the same colour. Such a colouring shall be called valid. Here, two triangles are said to be neighbouring if they share an edge.
Note: if they only share a vertex, then they are not neighbours.

For example, here is a valid colouring of the above grid:

A colouring C' which is obtained from a colouring C by rotation or reflection is considered distinct from C unless the two are identical.

How many distinct valid colourings are there for the above configuration?

### Code


public final class p189 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}

static public String run() {
return ""+solve("",8);
}

static long[][] count = new long[9][];
//第一递推式
public static long solve(String in, int limit) // in = AAA
{
long result = 0;
int len = in.length();
if (count[len] == null)//记忆化工作
count[len] = new long[pow(3, len)];
if (len == 0) {
result += solve("0", limit);
result += solve("1", limit);
result += solve("2", limit);
} else if (len < limit) {
char[] above = in.toCharArray(); // above = AAA
int z = 0;
int inverted = 0;
for (int i = 0; i < len; i++) {
z = z * 3;
z = z + ((3 - (above[0]) + (above[i])) % 3);
inverted = inverted * 3;
inverted = inverted
+ ((3 - (above[len - 1]) + (above[len - 1 - i])) % 3);
}
z = Math.min(z, inverted);
if (count[len][z] == 0) {
for (int i = 0; i < pow(2, len); i++) {
char[] below = new char[len]; // below = VVV
int k = i;
for (int j = 0; j < len; j++) {
int add = k % 2;
k = k >> 1;
below[j] = (char) ((above[j] + 1 + add) % 3 + '0');
}
result += solveB("", below, limit);
}
count[len][z] = result;
} else
result = count[len][z];
} else {
result += 1L;
}
return result;
}
//第二递推式
public static long solveB(String in, char[] below, int limit) {
long result = 0;
int len = in.length();
if (len == below.length) {
//已经填充完毕
result += solve(in + (char) (((int) below[len - 1] + 1) % 3 + '0'),
limit);
result += solve(in + (char) (((int) below[len - 1] + 2) % 3 + '0'),
limit);
} else if (len == 0 || below[len - 1] == below[len]) {
result += solveB(in + (char) (((int) below[len] + 1) % 3 + '0'),
below, limit);
result += solveB(in + (char) (((int) below[len] + 2) % 3 + '0'),
below, limit);
} else {
// 0, 1 -> 2
// 0, 2 -> 1
// 1, 2 -> 0
result += solveB(
in
+ (char) ((99 - (int) (below[len - 1] + below[len])) % 3 + '0'),
below, limit);
}
return result;
}
//i的j次方
public static int pow(int i, int j) {
if (j == 0)
return 1;
int result = 1;
for (int k = 0; k < j; k++)
result = result * i;
return result;
}
}
10834893628237824
435ms