以前、四色問題についての記事で、
「大人の塗り絵 パズル！」
というアプリと、その解き方についてご紹介しました。
しかし、四色問題のパズルに苦戦している方はまだまだ多いようなので、
今回は、
「FourColor2」
という別のアプリを用いて、前回よりもさらに詳しく四色問題のコツを解説しようと思います。
周囲が4色で囲まれてしまった時の対処法については、特に力を入れて書いていますので、
読者もこれを読んで、今まで諦めてしまっていた問題もサクサクと解いちゃってください。
四色問題の解き方とコツ
塗り絵パズルアプリ FourColor2
初めに、「FourColor2」について簡単に紹介すると、
という四色定理を利用した塗り絵パズルアプリです。
日本や中国、アメリカ各地の地図が問題として用意されていますが、
オリジナルの問題を作ることもできるのが特徴で、
自分で絵を描いてもよいですし、カメラで撮った写真を塗り絵に変換することもできます。
具体的な解き方と4色で囲まれた時の対処法
それでは早速、四色問題の具体的な解き方について解説していきます。
今回使用するのは、ノースダコタ州の地図です。
地図を塗り分ける場合、塗り絵のように配色の美しさを意識する必要はないので、
1色ずつまとめ塗りをしていくと早いです。
まずは、緑を使って、塗れる都市は全部塗ってしまいます。
このとき、州の端から徐々に緑を広げるイメージで塗っていくのがコツです。
次に黄色を使い、緑と同じように塗れる都市は全部塗ります。
できるだけたくさん塗れるように間を詰めて塗っていってくださいね。
次にピンクを使い、塗れる所は全部塗ります。
早くも完成に近づいてきました。
ところが、地図をよく見ると、1番の都市の色が州の周りの色と隣り合ってしまっています。
この問題を解決するために、
「ケンプ鎖（けんぷさ）」
と呼ばれるテクニックを使います。
ケンプ鎖とは、イギリスの数学者であるアルフレッド・B・ケンプが、
四色問題を証明するために用いた手法です。
この手法には不完全な点があったため、残念ながら証明は誤りとされてしまったのですが、
大抵の地図はこの手法で塗り分けられるので、知っておいて損はありません。
具体的な使い方ですが、以下の図をご覧ください。
現在、1番の都市が2～6番の4色の都市に囲まれてしまっています。
これを3色に減らすことができれば、1番を塗ることができるので、
5番を他の色に変えられないか検討していきます。
まず、黄色の5番を水色に変えるときは、
という都市の鎖を考えます（図の赤矢印）。
この鎖の上であれば、他の都市の色に影響を与えずに黄色と水色を交換することができるのです。
ただし、今回は鎖が2番とつながってしまったため、黄色と水色を交換しても、
5番が水色、2番が黄色になってあまり意味がありません。
そこで、次に黄色の5番をピンクに変えることを考えますが、このときは、
という鎖を考えます（図の青矢印）。
今度は、鎖が3番とつながらずに7番で途切れているため、5番と7番の色を交換することができます。
最後に、1番に黄色を塗って四色地図の完成です。
まとめ
いかがでしたでしょうか。
ケンプ鎖のテクニックを使うことで、周りが4色に囲まれてしまってもある程度は対応できるようになります。
「黄色とピンクの鎖が3番とつながっていたらどうするのか？」
という疑問が残りますが、その時は6番をピンクに、4番を水色に交換できないか検討していくことになります。
それでは、読者も「FourColor2」でケンプ鎖を駆使しながら遊んでみてください。
どうもありがとうございました！