地図の４色問題と決め打ちします。
♪ プログラムコード code
% cat tizu_4syoku.pl /*-------------------------------------------- 地図色塗り問題 M Hiroi さんのページから ┌─────────┐ │ ａ │ ├──┬───┬──┤ │ ｂ │ ｃ │ ｄ │ sea ├──┴─┬─┴──┤ │ ｅ │ ｆ │ └────┴────┘ a,b,d,e,f の周りは、sea とする。 図：簡単な地図 --------------------------------------------*/ /* 以下を参考にしました。 英語版：Prolog Programming for Artifical Intelligence (p28) 上の本には、バグがあります？たぶん 国々とSeaの関係が定義されていないからです。 */ % 配色可能な隣国の色の組( あか, あお, きいろ, みどり ) n( あか, あお ). n( あか, きいろ ). n( あか, みどり ). n( あお, あか ). n( あお, きいろ ). n( あお, みどり ). n( きいろ, あか ). n( きいろ, あお ). n( きいろ, みどり ). n( みどり, あか ). n( みどり, あお ). n( みどり, きいろ ). % a, b, c, d, e, f, Sea の配色 color_map( A, B, C, D, E, F, Sea ) :- Sea = あお, n(A, B), n(A, C), n(A, D), n(A, Sea), n(B, C), n(B, E), n(B, Sea), n(C, D), n(C, E), n(C, F), n(D, F), n(D, Sea), n(E, F), n(E, Sea), n(F, Sea), format( '~n -------------------- ~n' ).
実行例
% swipl -s tizu_4syoku.pl ?- color_map( A, B, C, D, E, F, Sea ). -------------------- A = E, E = あか, B = D, D = きいろ, C = Sea, Sea = あお, F = みどり ; -------------------- A = F, F = あか, B = D, D = きいろ, C = Sea, Sea = あお, E = みどり ; -------------------- A = E, E = あか, B = F, F = きいろ, C = Sea, Sea = あお, D = みどり ; -------------------- A = F, F = あか, B = きいろ, C = Sea, Sea = あお, D = E, E = みどり ; -------------------- A = あか, B = F, F = きいろ, C = Sea, Sea = あお, D = E, E = みどり ; -------------------- <略> ; false. ?- halt. %
解が存在することが分かる。
では、地図の３色問題と行きましょう。
♪ プログラムコード code
% cat tizu_3syoku.pl % 配色可能な隣国の色の組( あか, あお, きいろ) n( あか, あお ). n( あか, きいろ ). n( あお, あか ). n( あお, きいろ ).. n( きいろ, あか ). n( きいろ, あお ). % a, b, c, d, e, f, Sea の配色 color_map( A, B, C, D, E, F, Sea ) :- Sea = あお, n(A, B), n(A, C), n(A, D), n(A, Sea), n(B, C), n(B, E), n(B, Sea), n(C, D), n(C, E), n(C, F), n(D, F), n(D, Sea), n(E, F), n(E, Sea), n(F, Sea), format( '~n -------------------- ~n' ).
実行例
% swipl -s tizu_3syoku.pl ?- color_map( A, B, C, D, E, F, Sea ). false. ?- halt. %
解が存在しないことが分かりました。
つまり、４色(以上)あれば、地図を塗り分けることが出来るということです。