/* 

  Graceful labeling problem in Picat.

  From
  Belaid MOA, "Examples for Discrete Constraint Programming"
  http://www.docstoc.com/docs/23988870/Examples-for-Discrete-Constraint-Programming
  page 55ff
  """
  Given a tree T with m+1 nodes, and m edges find the possible labels in
  {0,1,...m} for the nodes such that the absolute value of the difference
  of the labels of the nodes related to each edge are all different. 
  """

  The example below is from page 58.
  There are 60 solutions to this problem. The solution shown on page 58
  is [0,6,1,3,4,5,2].


  Compare with the K4P2 Graceful graph model:
  http://www.hakank.org/picat/K4P2GracefulGraph2.pi


  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 ?=>
  
  NumNodes = 7,
  AdjacencyMatrix = new_matrix(NumNodes,NumNodes,
                                                  [
                                                   0,1,0,0,0,0,0,
                                                   1,0,1,0,0,0,0,
                                                   0,1,0,1,0,1,0,
                                                   0,0,1,0,1,0,0,
                                                   0,0,0,1,0,0,0,
                                                   0,0,1,0,0,0,1,
                                                   0,0,0,0,0,1,0
                                                   ]),
  Labels = new_list(NumNodes),
  Labels :: 0..NumNodes-1,


  all_different(Labels),
  foreach(I in 1..NumNodes, J in I+1..NumNodes)
    if AdjacencyMatrix[I,J] > 0 then
      foreach(K in 1..NumNodes, H in K+1..NumNodes)
        if AdjacencyMatrix[K,H] > 0, (K != I ; H != J) then
          (abs(Labels[I]-Labels[J]) #!= abs(Labels[H]-Labels[K]))
        end
      end
    end
  end,

  % Labels = [0,6,1,3,4,5,2], % the example solution

  solve(Labels),
  println(labels=Labels),
  fail,

  nl.

go => true.


%
% new_matrix(L,Rows,Cols,M)
%
% M is a Rows x Cols matrix representing the list L.
%
new_matrix(Rows,Cols,L) = M =>
  M = new_array(Rows,Cols),
  foreach(I in 0..Rows-1, J in 0..Cols-1)
    M[I+1,J+1] := L[I*Cols+J+1]
  end.