知恵袋で見つけた色の塗り分け問題をPythonで解いてみた。

　知恵袋で見つけた色の塗り分け(色分け)問題をPythonで解いてみました。(^_^;

　５色の絵の具を使って、下図のＡ,Ｂ,Ｃ,Ｄ,Ｅを塗り分ける。このとき
問１.異なる５色を使って塗り分ける方法は何通りか？
問２.異なる４色を使って塗り分ける方法は何通りか？
問３.異なる３色を使って塗り分ける方法は何通りか？

ただし、一部修正して、[問３]を追加しました。(^_^;

 +-------+---+
 |   C   |   |        C
 +---+---+ B |      ／|＼
 |   | A |   |     D--A--B
 | D +---+---+      ＼|／
 |   |   E   |        E
 +---+-------+

　隣接の様子を見るために右側にグラフを描いてみました。
　また、色をr(赤),b(青),w(白),y(黄),k(黒)としました。
P.S.
　同じ色が隣接したらスキップするために、隣接の様子を見てみると、Aから順に、次の通りです。
A-B,A-C,A-D,A-E
B-C,B-E
C-D
D-E
　ただし、B-A,C-A,C-B等は、それぞれ、A-B,A-C,B-Cでスキップするので省きました。
P.S.
　「if A==B or A==C or A==D or A==E: continue」のとこは、「if A in (B,C,D,E): continue」でもいいです。(^_^;

● Coloring1.py

# coding: UTF-8
# Coloring1.py

import itertools
from time import time

def main():
    tm=time()  # Timer Start
    cnt = [0]*4
    for p in itertools.product('rbwyk',repeat=5):
        A,B,C,D,E = p
        # 同じ色が隣接したらスキップ
        if A==B or A==C or A==D or A==E: continue
        if B==C or B==E: continue
        if C==D or D==E: continue
        # チェックを潜り抜けたものだけをカウント
        cnt[0]+=1
        n = len(set(p))     # 色の数
        # チェックを潜り抜けたものだけを表示
##        s = ''.join(p)
##        print("[%3d] %s : %d"%(cnt[0],s,len(set(p))))
        if n==5: cnt[1]+=1
        if n==4: cnt[2]+=1
        if n==3: cnt[3]+=1

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

if __name__ == '__main__':
    main()

●実行結果

(1) 120
(2) 240
(3) 60
Runtime : 0.000 [sec]

※参考URL
●四色定理の紹介と五色定理の証明 | 高校数学の美しい物語