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_undirected(X,Y) :- adjacent(X,Y).
adjacent_undirected(X,Y) :- adjacent(Y,X).

% 色が隣接区と違うことをチェック
safe_color(_, _, []).
safe_color(区, 色, [H-色H | T]) :-
    (adjacent_undirected(区, H) -> 色 \= 色H ; true),
    safe_color(区, 色, T).

% 順番に色割り当て、割り当て済みと矛盾がないか確認
assign_colors([], 割当済み, 割当済み).
assign_colors([区 | 残り], 割当済み0, 割当済み) :-
    color(色),
    safe_color(区, 色, 割当済み0),
    assign_colors(残り, [区-色 | 割当済み0], 割当済み).

% 結果の色リストを表示
print_colors([]).
print_colors([区-色 | 残り]) :-
    write(区), write(' -> '), write(色), nl,
    print_colors(残り).

% 実行開始
run :-
    順番 = [鶴見, 神奈川, 西, 中, 南, 港南,
            磯子, 金沢, 栄, 保土ケ谷, 旭, 瀬谷,
            泉, 戸塚, 都筑, 港北, 緑, 青葉],
    assign_colors(順番, [], 割当済み),
    write('4色で塗り分け可能'), nl,
    reverse(割当済み, 色リスト),
    print_colors(色リスト).

:- initialization(run).