% 色の定義
color(red).
color(green).
color(blue).
color(yellow).

% 隣接関係（双方向で定義）
adjacent(鶴見, 神奈川).
adjacent(鶴見, 港北).
adjacent(神奈川, 西).
adjacent(神奈川, 港北).
adjacent(西, 中).
adjacent(中, 南).
adjacent(南, 港南).
adjacent(港南, 磯子).
adjacent(磯子, 金沢).
adjacent(金沢, 栄).
adjacent(栄, 港南).
adjacent(中, 保土ケ谷).
adjacent(保土ケ谷, 西).
adjacent(保土ケ谷, 旭).
adjacent(旭, 瀬谷).
adjacent(瀬谷, 泉).
adjacent(泉, 戸塚).
adjacent(戸塚, 栄).
adjacent(都筑, 港北).
adjacent(都筑, 青葉).
adjacent(都筑, 緑).
adjacent(港北, 鶴見).
adjacent(緑, 青葉).
adjacent(保土ケ谷, 緑).

adjacent_undirected(X, Y) :- adjacent(X, Y).
adjacent_undirected(X, Y) :- adjacent(Y, X).

% 隣接区と色が違うことを確認
safe_color(_, _, []).
safe_color(District, Color, [OtherDistrict-OtherColor | Rest]) :-
    (adjacent_undirected(District, OtherDistrict) -> Color \= OtherColor ; true),
    safe_color(District, Color, Rest).

% 色割り当て。割当済みリストを渡してチェックしながら進む
assign_colors([], Assigned, Assigned).
assign_colors([D|Ds], AssignedSoFar, Assigned) :-
    color(Color),
    safe_color(D, Color, AssignedSoFar),
    assign_colors(Ds, [D-Color|AssignedSoFar], Assigned).

% 横浜市18区のリスト（探索順）
districts([鶴見, 神奈川, 西, 中, 南, 港南,
           磯子, 金沢, 栄, 保土ケ谷, 旭, 瀬谷,
           泉, 戸塚, 都筑, 港北, 緑, 青葉]).

% 結果の表示
print_colors([]).
print_colors([D-C|Rest]) :-
    format('~w -> ~w~n', [D, C]),
    print_colors(Rest).

% メイン実行ルーチン
run :-
    districts(Ds),
    assign_colors(Ds, [], Assigned),
    write('4色で塗り分け可能です。'), nl,
    reverse(Assigned, AssignedReversed),
    print_colors(AssignedReversed).

:- initialization(run).