/* 

  Coloring problem in Picat.

  From 
  Katta G. Murty: "Optimization Models for Decision Making", page 344f
  http://ioe.engin.umich.edu/people/fac/books/murty/opti_model/junior-7.pdf


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.


main => go.

go ?=>
  data(1,Countries,Graph),
  N = Countries.len,
  NumNodes = Graph.len,
  
  % number of colors used, to be minimized
  NumColors :: 1..N, 

  % x what color of each country
  X = new_list(N),
  X :: 1..N,

  % No adjacent countries can have the same color
  foreach(I in 1..NumNodes)
    element(Graph[I,1],X,C1),
    element(Graph[I,2],X,C2),
    C1 #!= C2
  end,
  
  % upper limit on the number of colors
  foreach(I in 1..N)
     X[I] #<= NumColors
  end,

  % symmetry breaking
  X[1] #= 1,

  solve($[min(NumColors)], X),

  println(numColors=NumColors),
  println(x=X),
  
  nl.

go => true.
%
%
%
data(1,Countries,Graph) =>
  Countries = ["Belgium", "Denmark", "France", "Germany", "Netherlands", "Luxembourg"],

  %
  % Neighbours
  %
  Graph = {
           {3, 1},
           {3, 6},
           {3, 4},
           {6, 4},
           {6, 1},
           {1, 5},
           {1, 4},
           {4, 5},
           {4, 2}}.