fork download
copy 
  1. % 色の定義
  2. color(red).
  3. color(green).
  4. color(blue).
  5. color(yellow).
  6.  
  7. % 隣接関係（双方向で定義）
  8. adjacent(鶴見, 神奈川).
  9. adjacent(鶴見, 港北).
  10. adjacent(神奈川, 西).
  11. adjacent(神奈川, 港北).
  12. adjacent(西, 中).
  13. adjacent(中, 南).
  14. adjacent(南, 港南).
  15. adjacent(港南, 磯子).
  16. adjacent(磯子, 金沢).
  17. adjacent(金沢, 栄).
  18. adjacent(栄, 港南).
  19. adjacent(中, 保土ケ谷).
  20. adjacent(保土ケ谷, 西).
  21. adjacent(保土ケ谷, 旭).
  22. adjacent(旭, 瀬谷).
  23. adjacent(瀬谷, 泉).
  24. adjacent(泉, 戸塚).
  25. adjacent(戸塚, 栄).
  26. adjacent(都筑, 港北).
  27. adjacent(都筑, 青葉).
  28. adjacent(都筑, 緑).
  29. adjacent(港北, 鶴見).
  30. adjacent(緑, 青葉).
  31. adjacent(保土ケ谷, 緑).
  32.  
  33. adjacent_undirected(X, Y) :- adjacent(X, Y).
  34. adjacent_undirected(X, Y) :- adjacent(Y, X).
  35.  
  36. % 隣接区と色が違うことを確認
  37. safe_color(_, _, []).
  38. safe_color(District, Color, [OtherDistrict-OtherColor | Rest]) :-
  39.     (adjacent_undirected(District, OtherDistrict) -> Color \= OtherColor ; true),
  40.     safe_color(District, Color, Rest).
  41.  
  42. % 色割り当て。割当済みリストを渡してチェックしながら進む
  43. assign_colors([], Assigned, Assigned).
  44. assign_colors([D|Ds], AssignedSoFar, Assigned) :-
  45.     color(Color),
  46.     safe_color(D, Color, AssignedSoFar),
  47.     assign_colors(Ds, [D-Color|AssignedSoFar], Assigned).
  48.  
  49. % 横浜市18区のリスト（探索順）
  50. districts([鶴見, 神奈川, 西, 中, 南, 港南,
  51.            磯子, 金沢, 栄, 保土ケ谷, 旭, 瀬谷,
  52.            泉, 戸塚, 都筑, 港北, 緑, 青葉]).
  53.  
  54. % 結果の表示
  55. print_colors([]).
  56. print_colors([D-C|Rest]) :-
  57.     format('~w -> ~w~n', [D, C]),
  58.     print_colors(Rest).
  59.  
  60. % メイン実行ルーチン
  61. run :-
  62.     districts(Ds),
  63.     assign_colors(Ds, [], Assigned),
  64.     write('4色で塗り分け可能です。'), nl,
  65.     reverse(Assigned, AssignedReversed),
  66.     print_colors(AssignedReversed).
  67.  
  68. :- initialization(run).
  69.  
Success #stdin #stdout #stderr 0.03s 7076KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4色で塗り分け可能です。
鶴見 -> red
神奈川 -> green
西 -> red
中 -> green
南 -> red
港南 -> green
磯子 -> red
金沢 -> green
栄 -> red
保土ケ谷 -> blue
旭 -> red
瀬谷 -> green
泉 -> red
戸塚 -> green
都筑 -> red
港北 -> blue
緑 -> green
青葉 -> blue
stderr
copy 
ERROR: '$runtoplevel'/0: Undefined procedure: program/0
   Exception: (3) program ? EOF: exit
https://ideone.com/UtTSLI
language:
Prolog (swi 7.6.4)
created:
8 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!