正八面体をn色で塗るパターン数

　正八面体（regular octahedron）をn色で塗るパターン数をポリアの数え上げで数えてみました。もはや正多面体に愛情すら感じるようになってきました。まさにプラトニックラブです。

前回の隣接する面が写像前後で変わらないという性質を使って、対称群（symmetric group）から正多面体の回転に対応する元のみ抽出するという技を応用して正八面体に適用してみました。

対称群すべて列挙して・・というやり方ではなくて、DFSで枝刈りしながら探索としてみました。かなり大きな枝刈りが出来ていると思うので、この方法を使えば正二十面体も攻略できそうです。

検算の結果[1, 2]、正しく計算できていました。

#include <cassert>
#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

// faces that shares an edges (clockwise)
int adjFaces[][3] = {
    {3, 1, 7},
    {0, 2, 4},
    {1, 3, 5},
    {0, 6, 2},
    {1, 5, 7},
    {2, 6, 4},
    {3, 7, 5},
    {0, 4, 6}
};

vector<vector<int> > group;

bool isRotate(int a[]) {
    for (int i = 0; i < 8; i++) {
        if (a[i] == -1)          // this face is not aligned yet
            continue;

        int p = -1;
        for (int j = 0; j < 3; j++) {
            if (a[adjFaces[i][j]] != -1) {
                p = j;
                break;
            }
        }

        if (p == -1)              // no adjacent faces are not aligned yet
            continue;

        int q = -1;
        for (int j = 0; j < 3; j++) {
            if (a[adjFaces[i][p]] == adjFaces[a[i]][j]) {
                q = j;
                break;
            }
        }
        
        if (q == -1)              // wrong alignment
            return false;

        for (int j = 0; j < 3; j++) {
            if (a[adjFaces[i][(p+j)%3]] == -1)   // not aligned yet
                continue;
            if (a[adjFaces[i][(p+j)%3]] != adjFaces[a[i]][(q+j)%3])
                return false;
        }
    }

    return true;
}

void dfs(int p[], int k, int mask) {
    if (!isRotate(p))
        return;

    if (__builtin_popcountll(mask) == 8)
        group.push_back(vector<int>(p, p+8));

    for (int i = 0; i < 8; i++) {
        if (mask >> i & 1)
            continue;
        p[k] = i;
        dfs(p, k+1, mask|1<<i);
        p[k] = -1;
    }
}

long long pow(long long x, long long p) {
    long long ret = 1;
    while (p) {
        if (p & 1)
            ret = ret * x;
        x = x * x;
        p >>= 1;
    }
    return ret;
}

int cycleNum(const vector<int> &p) {
    bool vis[8] = {};
    
    int ret = 0;
    for (int i = 0; i < 8; i++) {
        if (vis[i])
            continue;
        ++ret;
        for (int j = i; !vis[j]; j = p[j])
            vis[j] = true;
    }

    return ret;
}

long long solve(int color) {
    int p[8];
    memset(p, -1, sizeof(p));

    dfs(p, 0, 0);
    assert(group.size() == 24);
    
    long long sum = 0;
    for (size_t i = 0; i < group.size(); i++) {
        sum += pow(color, cycleNum(group[i]));
    }

    return sum / group.size();
}

long long getAnswer(int c) {
    return (6*pow(c, 2) + 17*pow(c, 4) + pow(c, 8)) / 24;
} 

int main(int argc, char **argv) {
    int c;
    cin >> c;

    long long ret = solve(c);
    assert(ret == getAnswer(c));
    cout << ret << endl;

    return 0;
}

参考URL

[1] Polyhedron Coloring -- from Wolfram MathWorld
[2] Octahedral symmetry - Wikipedia, the free encyclopedia