知恵袋の正八面体の色の塗り分け問題をPythonで解いてみた。

　知恵袋の正八面体の色の塗り分け問題をPythonで解いてみました。(^_^;

　正八面体の各面を８色で塗る塗り方は何通りあるか。ただし、ひっくり返したり、回転させたりして一致する塗り方は同じとみなす。

　正八面体の各面に次のようにA〜Hと名前を付けました。また、色の名前をa〜hとしました。(^_^;

         ／＼
       ／ F  ＼
     ＋－－－－＋
   ／｜＼ A  ／｜＼
 ／D ｜G ＼／ C｜ H＼
 ＼  ｜  ／＼  ｜  ／
   ＼｜／ E  ＼｜／
     ＋－－－－＋
       ＼ B  ／
         ＼／

　ちょっと遅いですね。ちなみに、Javaでやっても、数秒しか速くならなかったです。(^_^;
　1番目と２番目の参考URLによると、正多面体の塗り分け方の総数には公式があるようです。

●正多面体の塗り分け方の総数の公式
　正m角形で構成される正n面体の塗り分け方の総数は、 $\frac{(n-1)!}{m}$ 通りである。

　 $\frac{(8-1)!}{3}=7!\div3=7\times6\times5\times4\times3\times2\times1\div3=1680$

● OctahedronColoring1.py

# coding: UTF-8
# OctahedronColoring1.py

import itertools
from time import time

DB = []     # 発見したパターンの記録用
# 回転させて一致する塗り方のパターンか調べる
def isSamePat(p):
    A,B,C,D,E,F,G,H = p
    S = []
    T = [(A,B,C,D,E,F,G,H),(F,E,H,G,C,D,A,B),(C,D,H,G,B,A,E,F)]
    for t in T:
        s = "%s%s|%s%s|%s%s|%s%s|"%t*2
        S.append(s+s[::-1])

    for d in DB:
        for s in S:
            if d in s: return True

    DB.append("%s%s|%s%s|%s%s|%s%s"%p)
    return False

def main():
    tm=time()  # Timer Start
    P = 'abcdefgh'  # 色
    N = 8           # 色数
    c = 0

    DB = []
    for p in itertools.permutations(P):
        if isSamePat(p): continue   # 回転させて同じパターンならスキップ
        # チェックを潜り抜けたものだけをカウント
        c+=1

    print(c)
    print("Runtime : %.3f [sec]"%(time()-tm))   # Timer Stop & Disp

if __name__ == '__main__':
    main()

●実行結果

1680
Runtime : 24.730 [sec]

※参考URL
●塗り分けの方法
●正多面体の思考の塗り分け　〜ちょっと変えたn色問題〜
●知恵袋の立方体の色の塗り分け問題をPythonで解いてみた。
●知恵袋の正八面体の色の塗り分け問題をPythonで解いてみた。(2)