/*

  Map coloring in Picat.

  Simple map coloring problem.


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

*/

import cp.

main => go.

go =>
        connections(Connections), 
        NumColors = 4,
        mapx(Connections, Countries, NumColors),
        writeln(Countries),

        All = findall(Countries2, $mapx(Connections, Countries2, NumColors)),
        Len = length(All),
        writef("It was %d different solutions using %d colors:\n", Len,NumColors),
        writeln(All).


%
% optimize the number of used colors
%
go2 =>
        connections(Connections), 
        NumColors = 5,
        map2(Connections, Countries, NumColors, MinColors),
        writeln(Countries),
        writef("We used %d colors\n", MinColors).



mapx(Connections, Countries, NumColors) =>

        N = Connections.length, 
        Countries = new_list(N),
        Countries :: 1..NumColors,
        foreach(C1 in 1..N, C2 in C1+1..N) 
                    if Connections[C1,C2] == 1 then
                        Countries[C1] #!= Countries[C2]
                    end
        end,

        % symmetry breaking
        Countries[1] #= 1,
        Countries[2] #=< 2,

        solve(Countries).


% optimization
map2(Connections, Countries, NumColors, MinColors) =>

        N = Connections.length, 
        Countries = new_list(N),
        Countries :: 1..NumColors,
        MinColors :: 1..NumColors, % to optimize

        MinColors #= max(Countries),
        foreach(C1 in 1..N, C2 in C1+1..N)
            if Connections[C1,C2] == 1 then
                Countries[C1] #!= Countries[C2]
             end
        end,

        % symmetry breaking
        Countries[1] #= 1,
        Countries[2] #=< 2,

        solve([$min(MinColors)], Countries).


% Connections between these countries:
% [belgium, denmark, france, germany, netherlands, luxembourg]
connections(A) => 
         A = [[0, 0, 1, 1, 1, 1],
             [0, 0, 0, 1, 0, 0],
             [1, 0, 0, 1, 1, 0],
             [1, 1, 1, 0, 1, 1],
             [1, 0, 1, 1, 0, 0],
             [1, 0, 0, 1, 0, 0]].