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(保土ケ谷, 緑).
 
different(区1-色1, 区2-色2) :-
    (adjacent(区1, 区2); adjacent(区2, 区1)) -> 色1 \= 色2 ; true.
 
valid_coloring(Vars) :-
    % 隣接している区の間で色が異なる
    forall(
        (member(A, Vars), member(B, Vars), A \= B),
        different(A, B)
    ).
 
try_coloring(Result) :-
    Vars = [
        鶴見-A, 神奈川-B, 西-C, 中-D, 南-E, 港南-F,
        磯子-G, 金沢-H, 栄-I, 保土ケ谷-J, 旭-K, 瀬谷-L,
        泉-M, 戸塚-N, 都筑-O, 港北-P, 緑-Q, 青葉-R
    ],
    Colors = [red, green, blue, yellow],
    member(A, Colors), member(B, Colors), member(C, Colors), member(D, Colors),
    member(E, Colors), member(F, Colors), member(G, Colors), member(H, Colors),
    member(I, Colors), member(J, Colors), member(K, Colors), member(L, Colors),
    member(M, Colors), member(N, Colors), member(O, Colors), member(P, Colors),
    member(Q, Colors), member(R, Colors),
    Result = [
        鶴見-A, 神奈川-B, 西-C, 中-D, 南-E, 港南-F,
        磯子-G, 金沢-H, 栄-I, 保土ケ谷-J, 旭-K, 瀬谷-L,
        泉-M, 戸塚-N, 都筑-O, 港北-P, 緑-Q, 青葉-R
    ],
    valid_coloring(Result), !. % 見つかったら即終了
 
print_colors([]).
print_colors([区-色 | 残り]) :-
    write(区), write(' -> '), write(色), nl,
    print_colors(残り).
 
:- try_coloring(Result), write('4色で塗り分け可能'), nl, print_colors(Result).
 

Y29sb3IocmVkKS4KY29sb3IoZ3JlZW4pLgpjb2xvcihibHVlKS4KY29sb3IoeWVsbG93KS4KCmFkamFjZW50KOm2tOimiywg56We5aWI5bedKS4KYWRqYWNlbnQo56We5aWI5bedLCDopb8pLgphZGphY2VudCjopb8sIOS4rSkuCmFkamFjZW50KOS4rSwg5Y2XKS4KYWRqYWNlbnQo5Y2XLCDmuK/ljZcpLgphZGphY2VudCjmuK/ljZcsIOejr+WtkCkuCmFkamFjZW50KOejr+WtkCwg6YeR5rKiKS4KYWRqYWNlbnQo6YeR5rKiLCDmoIQpLgphZGphY2VudCjmoIQsIOa4r+WNlykuCmFkamFjZW50KOS4rSwg5L+d5Zyf44Kx6LC3KS4KYWRqYWNlbnQo5L+d5Zyf44Kx6LC3LCDopb8pLgphZGphY2VudCjkv53lnJ/jgrHosLcsIOaXrSkuCmFkamFjZW50KOaXrSwg54Cs6LC3KS4KYWRqYWNlbnQo54Cs6LC3LCDms4kpLgphZGphY2VudCjms4ksIOaIuOWhmikuCmFkamFjZW50KOaIuOWhmiwg5qCEKS4KYWRqYWNlbnQo6YO9562RLCDmuK/ljJcpLgphZGphY2VudCjpg73nrZEsIOmdkuiRiSkuCmFkamFjZW50KOmDveetkSwg57eRKS4KYWRqYWNlbnQo5riv5YyXLCDnpZ7lpYjlt50pLgphZGphY2VudCjnt5EsIOmdkuiRiSkuCmFkamFjZW50KOa4r+WMlywg6ba06KaLKS4KYWRqYWNlbnQo5L+d5Zyf44Kx6LC3LCDnt5EpLgoKZGlmZmVyZW50KOWMujEt6ImyMSwg5Yy6Mi3oibIyKSA6LQogICAgKGFkamFjZW50KOWMujEsIOWMujIpOyBhZGphY2VudCjljLoyLCDljLoxKSkgLT4g6ImyMSBcPSDoibIyIDsgdHJ1ZS4KCnZhbGlkX2NvbG9yaW5nKFZhcnMpIDotCiAgICAlIOmao+aOpeOBl+OBpuOBhOOCi+WMuuOBrumWk+OBp+iJsuOBjOeVsOOBquOCiwogICAgZm9yYWxsKAogICAgICAgIChtZW1iZXIoQSwgVmFycyksIG1lbWJlcihCLCBWYXJzKSwgQSBcPSBCKSwKICAgICAgICBkaWZmZXJlbnQoQSwgQikKICAgICkuCgp0cnlfY29sb3JpbmcoUmVzdWx0KSA6LQogICAgVmFycyA9IFsKICAgICAgICDptrTopostQSwg56We5aWI5bedLUIsIOilvy1DLCDkuK0tRCwg5Y2XLUUsIOa4r+WNly1GLAogICAgICAgIOejr+WtkC1HLCDph5HmsqItSCwg5qCELUksIOS/neWcn+OCseiwty1KLCDml60tSywg54Cs6LC3LUwsCiAgICAgICAg5rOJLU0sIOaIuOWhmi1OLCDpg73nrZEtTywg5riv5YyXLVAsIOe3kS1RLCDpnZLokYktUgogICAgXSwKICAgIENvbG9ycyA9IFtyZWQsIGdyZWVuLCBibHVlLCB5ZWxsb3ddLAogICAgbWVtYmVyKEEsIENvbG9ycyksIG1lbWJlcihCLCBDb2xvcnMpLCBtZW1iZXIoQywgQ29sb3JzKSwgbWVtYmVyKEQsIENvbG9ycyksCiAgICBtZW1iZXIoRSwgQ29sb3JzKSwgbWVtYmVyKEYsIENvbG9ycyksIG1lbWJlcihHLCBDb2xvcnMpLCBtZW1iZXIoSCwgQ29sb3JzKSwKICAgIG1lbWJlcihJLCBDb2xvcnMpLCBtZW1iZXIoSiwgQ29sb3JzKSwgbWVtYmVyKEssIENvbG9ycyksIG1lbWJlcihMLCBDb2xvcnMpLAogICAgbWVtYmVyKE0sIENvbG9ycyksIG1lbWJlcihOLCBDb2xvcnMpLCBtZW1iZXIoTywgQ29sb3JzKSwgbWVtYmVyKFAsIENvbG9ycyksCiAgICBtZW1iZXIoUSwgQ29sb3JzKSwgbWVtYmVyKFIsIENvbG9ycyksCiAgICBSZXN1bHQgPSBbCiAgICAgICAg6ba06KaLLUEsIOelnuWliOW3nS1CLCDopb8tQywg5LitLUQsIOWNly1FLCDmuK/ljZctRiwKICAgICAgICDno6/lrZAtRywg6YeR5rKiLUgsIOaghC1JLCDkv53lnJ/jgrHosLctSiwg5petLUssIOeArOiwty1MLAogICAgICAgIOaziS1NLCDmiLjloZotTiwg6YO9562RLU8sIOa4r+WMly1QLCDnt5EtUSwg6Z2S6JGJLVIKICAgIF0sCiAgICB2YWxpZF9jb2xvcmluZyhSZXN1bHQpLCAhLiAlIOimi+OBpOOBi+OBo+OBn+OCieWNs+e1guS6hgoKcHJpbnRfY29sb3JzKFtdKS4KcHJpbnRfY29sb3JzKFvljLot6ImyIHwg5q6L44KKXSkgOi0KICAgIHdyaXRlKOWMuiksIHdyaXRlKCcgLT4gJyksIHdyaXRlKOiJsiksIG5sLAogICAgcHJpbnRfY29sb3JzKOaui+OCiikuCgo6LSB0cnlfY29sb3JpbmcoUmVzdWx0KSwgd3JpdGUoJzToibLjgafloZfjgorliIbjgZHlj6/og70nKSwgbmwsIHByaW50X2NvbG9ycyhSZXN1bHQpLgo=