色の塗り分け問題をアルゴリズムで解いてみる

はじめに

身近なもので何かないかなと考えていたのですが、昔やった色塗り問題を思い出しました。例えば下のように3マスあって、3色で色を塗り分けた場合、塗り方が何通りあるかです。

マスを区別するので全体は3×3×3=27通りです。この時、隣同士で色が重複しない塗り方は何通りあるか考えてみましょう。
・・・正直アルゴリズム使わなくても、ごり押しで求められます(★の部分で12通り)。

でもせっかくなので、アルゴリズムを使って考えてみることにしました。

アルゴリズム的な何かを書いてみる

import itertools

#重複を許して3種類の組み合わせを作成(赤：0　黄：1　青：2)
comb = itertools.product(range(3), repeat=3) 
l_comb = list(comb) #リスト化

result = []

#組み合わせの1番目と2番目、もしくは2番目と3番目が同じ場合は削除
for i in range(len(l_comb)):
    if l_comb[i][0] == l_comb[i][1] or l_comb[i][1] == l_comb[i][2]:
        continue
    else:
        result.append(l_comb[i])

#得られた組み合わせとその数を表示
print(result)
print(len(result)) 

まず組み合わせを作成しています。そこから1番目-2番目もしくは2番目-3番目の値が被っていないものだけを、新しいリストに入れて作りました。
ちゃんと12個作成されたことがわかります。

まとめ

アルゴリズムってその道のプロじゃないと書けないかなと思っていたのですが、素人でもやりようによっては作れることがわかってよかったです。

参考

https://hibiki-press.tech/python/itertools/1796
https://docs.python.org/ja/3/library/itertools.html#itertools.product