「地図の配色問題」は、平面上にある隣り合った地域が同じ色にならないように塗り分けるという問題です。1976 年にアッペル氏とハーケン氏により、どんな場合でも 4 色あれば塗り分けできることが証明されました。これを「四色問題」といいます。今回は、次に示す簡単な地図を塗り分けてみてください。
┌──────┬──────┐
│ Ａ │ Ｂ │
│ ┌──┬─┴─┬──┐ │
│ │ │ Ｄ │ │ │
│ │ Ｃ ├─┬─┤ Ｅ │ │
│ │ │ │ │ │ │
│ ├──┤Ｇ│Ｈ├──┤ │
│ │ │ │ │ │ │
│ │ Ｆ ├─┴─┤ Ｉ │ │
│ │ │ Ｊ │ │ │
│ ├──┴─┬─┴──┤ │
│ │ Ｋ │ Ｌ │ │
│ └────┴────┴─┤
│ │
└─────────────┘
図 : 簡単な地図
この程度の大きさの地図であれば、私達でも解くことができると思います。気分転換や息抜きのときに考えてみてください。ちなみに、3 色では解けません。
それではプログラムを作りましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。下の地図の配色は、単純な深さ優先探索で簡単に解くことができます。順番に地域の色を決めていきますが、このときに隣接している地域と異なる色を選びます。もし、色を選ぶことができなければ、バックトラックして前の地域に戻り違う色を選びます。
┌──────┬──────┐
│ Ａ:0 │ Ｂ:1 │
│ ┌──┬─┴─┬──┐ │
│ │ │ Ｄ:3 │ │ │
│ │ Ｃ ├─┬─┤ Ｅ │ │
│ │ :2 │ │ │ :4 │ │
│ ├──┤Ｇ│Ｈ├──┤ │
│ │ │:6│:7│ │ │
│ │ Ｆ ├─┴─┤ Ｉ │ │
│ │ :5 │ Ｊ:9 │ :8 │ │
│ ├──┴─┬─┴──┤ │
│ │ Ｋ:10 │ Ｌ:11 │ │
│ └────┴────┴─┤
│ │
└─────────────┘
図 : 簡単な地図
図に示したように、各地域を番号で表すことにします。地図はグラフで表すことができるので、いつものように「隣接リスト」を使いましょう。地域の色は配列 (Python のリスト) に格納します。まだ色を塗っていない状態を 0 で表し、1 から 4 までの数値で色を表します。たとえば、地域Ｇに色 1 を塗るのであれば、隣接の地域で色 1 が使われていないことを確認すればいいわけです。
それから、塗り分けに必要な色の種類は、反復深化を使って求めます。つまり、2, 3, 4 と色の種類を増やして、実際に塗り分けることができるか試していくわけです。
プログラムは次のようになります。
リスト : 地図の配色問題
# 隣接リスト
adjacent = [
[1, 2, 3, 5, 10, 11], # 0
[0, 3, 4, 8, 11], # 1
[0, 3, 5, 6], # 2
[0, 1, 2, 4, 6, 7], # 3
[1, 3, 7, 8], # 4
[0, 2, 6, 9, 10], # 5
[2, 3, 5, 7, 9], # 6
[3, 4, 6, 8, 9], # 7
[1, 4, 7, 9, 11], # 8
[5, 6, 7, 8, 10, 11], # 9
[0, 5, 9, 11], # 10
[0, 1, 8, 9, 10] # 11
]
# 同じ色がないかチェック
def check_same_color(n, c, cs):
for x in adjacent[n]:
if cs[x] == c: return False
return True
# 深さ優先探索
def dfs(n, max_color, cs):
if n == len(adjacent):
print(f'{max_color} colors: {cs}')
else:
for c in range(1, max_color + 1):
if not check_same_color(n, c, cs): continue
cs[n] = c
dfs(n + 1, max_color, cs)
cs[n] = 0
関数 dfs() は単純な深さ優先探索です。引数 n は地域の番号を表し、max_color は色の種類を表します。引数 cs はリストで、地域の色をセットします。cs は 0 に初期化して渡します。地域Ａ (0) から色を割り当てていき、関数 check_same_color() で隣接の地域に同じ色が使われていないかチェックします。あとは、とくに難しいところはないでしょう。
それではプログラムを実行してみましょう。次のように、色の種類を増やして地図を塗り分けることができるか試していきます。
リスト : 反復深化
def solver():
for c in range(2, 5):
dfs(0, c, [0] * len(adjacent))
その結果、4 色で 216 通りの解が出力されました。このプログラムでは重複解のチェックを行っていないので、多数の解が出力されます。地域Ａの色を 1 に限定すると 54 通りの解となります。最初に表示される解を示します。
┌──────┬──────┐
│ ● │ ● │
│ ┌──┬─┴─┬──┐ │
│ │ │ ● │ │ │
│ │ ● ├─┬─┤ ● │ │
│ │ │ │ │ │ │
│ ├──┤●│●├──┤ │
│ │ │ │ │ │ │
│ │ ● ├─┴─┤ ● │ │
│ │ │ ● │ │ │
│ ├──┴─┬─┴──┤ │
│ │ ● │ ● │ │
│ └────┴────┴─┤
│ │
└─────────────┘
図 : 地図の色分け解答例
A B C D E F G H I J K L
-------------------------
4 colors: 1 2 2 3 1 3 4 2 3 1 2 4
今回は 12 の地域しかないので、単純な深さ優先探索で簡単に解くことができます。ところが、地域の数が増えるにしたがい、探索に時間がかかるようになります。数百ヶ国もある地図となると、単純な深さ優先探索で (現実的な時間で) 解くのは難しいと思います。四色問題が証明されたとはいえ、実際に大きな地図を塗り分けるのは難しいことですね。