「地図の配色問題」は、平面上にある隣り合った地域が同じ色にならないように塗り分けるという問題です。1976 年にアッペルとハーケンにより、どんな場合でも 4 色あれば塗り分けできることが証明されました。これを 四色問題 といいます。今回は、次に示す簡単な地図を塗り分けてみてください。
┌──────┬──────┐
│ Ａ │ Ｂ │
│ ┌──┬─┴─┬──┐ │
│ │ │ Ｄ │ │ │
│ │ Ｃ ├─┬─┤ Ｅ │ │
│ │ │ │ │ │ │
│ ├──┤Ｇ│Ｈ├──┤ │
│ │ │ │ │ │ │
│ │ Ｆ ├─┴─┤ Ｉ │ │
│ │ │ Ｊ │ │ │
│ ├──┴─┬─┴──┤ │
│ │ Ｋ │ Ｌ │ │
│ └────┴────┴─┤
│ │
└─────────────┘
図：簡単な地図
この程度の大きさの地図であれば、私達でも解くことができると思います。気分転換や息抜きのときに考えてみてください。ちなみに、3 色では解けません。
それではプログラムを作りましょう。使用する言語は Perl です。下の地図の配色は、単純な深さ優先探索で簡単に解くことができます。順番に地域の色を決めていきますが、このときに隣接している地域と異なる色を選びます。もし、色を選ぶことができなければ、バックトラックして前の地域に戻り違う色を選びます。
┌──────┬──────┐
│ Ａ:0 │ Ｂ:1 │
│ ┌──┬─┴─┬──┐ │
│ │ │ Ｄ:3 │ │ │
│ │ Ｃ ├─┬─┤ Ｅ │ │
│ │ :2 │ │ │ :4 │ │
│ ├──┤Ｇ│Ｈ├──┤ │
│ │ │:6│:7│ │ │
│ │ Ｆ ├─┴─┤ Ｉ │ │
│ │ :5 │ Ｊ:9 │ :8 │ │
│ ├──┴─┬─┴──┤ │
│ │ Ｋ:10 │ Ｌ:11 │ │
│ └────┴────┴─┤
│ │
└─────────────┘
図：簡単な地図
図に示したように、各地域を番号で表すことにします。地図はグラフで表すことができるので、いつものように「隣接リスト」を使いましょう。地域の色は配列 @color に格納します。まだ色を塗っていない状態を 0 で表し、1 から 4 までの数値で色を表します。たとえば、地域Ｇに色 1 を塗るのであれば、隣接の地域で色 1 が使われていないことを確認すればいいわけです。
それから、塗り分けに必要な色の種類は、反復深化を使って求めます。つまり、2, 3, 4 と色の種類を増やして、実際に塗り分けることができるか試していくわけです。
プログラムは次のようになります。
リスト：地図の配色問題
# 色
@color = ();
# 隣接リスト
@neighbors = (
[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
);
# 同じ色がないかチェック
sub check_same_color {
my ($node, $color) = @_;
foreach $region ( @{$neighbors[$node]} ){
return 0 if $color[$region] == $color;
}
1;
}
# 深さ優先探索
sub search {
my ($node, $color) = @_;
if( $node == @neighbors ){
print "$color colors: @color\n";
} else {
my $c;
for( $c = 1; $c <= $color; $c++ ){
if( &check_same_color( $node, $c ) ){
$color[$node] = $c;
&search( $node + 1, $color );
$color[$node] = 0;
}
}
}
}
関数 search は単純な深さ優先探索です。引数 $node は地域の番号を表し、$color は色の種類を表します。地域Ａ (0) から色を割り当てていき、関数 check_same_color で隣接の地域に同じ色が使われていないかチェックします。あとは、とくに難しいところはないでしょう。
それではプログラムを実行してみましょう。次のように、色の種類を増やして地図を塗り分けることができるか試していきます。
# 実行する &search( 0, 2 ); &search( 0, 3 ); &search( 0, 4 );
その結果、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 の地域しかないので、単純な深さ優先探索で簡単に解くことができます。ところが、地域の数が増えるにしたがい、探索に時間がかかるようになります。
M.Kamadaさん の 日記 と掲示板に四色問題の話があります。それによると、四色問題では「ムーア(Edward F. Moore)の地図」というのが有名で、342ヶ国と846ヶ国の 2 種類の地図があるそうです。数百ヶ国もある地図となると、単純な深さ優先探索では現実的な時間で解くことはできないでしょう。
四色問題が証明されたとはいえ、実際に大きな地図を塗り分けるのは難しいことですね。