/*

  Crossword problem in Picat.

  This is a standard example for constraint logic programming. See e.g.
 
  http://www.cis.temple.edu/~ingargio/cis587/readings/constraints.html
  """
  We are to complete the puzzle
 
       1   2   3   4   5
     +---+---+---+---+---+       Given the list of words:
   1 | 1 |   | 2 |   | 3 |             AFT     LASER
     +---+---+---+---+---+             ALE     LEE
   2 | # | # |   | # |   |             EEL     LINE
     +---+---+---+---+---+             HEEL    SAILS
   3 | # | 4 |   | 5 |   |             HIKE    SHEET
     +---+---+---+---+---+             HOSES   STEER
   4 | 6 | # | 7 |   |   |             KEEL    TIE
     +---+---+---+---+---+             KNOT
   5 | 8 |   |   |   |   |
     +---+---+---+---+---+       
   6 |   | # | # |   | # |       The numbers 1,2,3,4,5,6,7,8 in the crossword
     +---+---+---+---+---+       puzzle correspond to the words 
                                                   that will start at those locations.
  """

  The model was inspired by Sebastian Brand's Array Constraint 
  cross word example but it is slightly generalized
  * http://www.cs.mu.oz.au/~sbrand/project/ac/
  * http://www.cs.mu.oz.au/~sbrand/project/ac/examples.pl


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

*/

import cp.

main => go.

go =>
   overlapping(Overlappings),
   NumOverlappings = Overlappings.length,
   words(Words),
   NumWords = length(Words),

   ESize = 8,

   % decision variables
   E = new_list(ESize),
   E :: 1..NumWords,

   all_different(E),

   foreach(I in 1..NumOverlappings)
        % the overlappings
        O1 = Overlappings[I,1], % first word
        O2 = Overlappings[I,2], % position in first word
        O3 = Overlappings[I,3], % second word
        O4 = Overlappings[I,4], % position in second word

        % fetch the two E variables to use
        nth(O1,E,E1),
        nth(O3,E,E2), 

        % Get the words
        nth(E1,Words,Word1),
        nth(E2,Words,Word2),

        Word1 != Word2,

        % The same char in the overlapping.
        nth(O2,Word1,C),
        nth(O4,Word2,C)          
       
   end,
   
   solve(E),

   writeln(e=E),
   foreach(I in 1..ESize)
        Word = Words[E[I]],
        printf("%d (%d): ",I,E[I]),
        print_word(Word),
        writef("\n")
   end.




print_word(Word) =>
   foreach(W in Word)
      if ground(W) then
         printf("%w", W)
      end
   end.


%
% Definition of the words. A _ is used to fill the row.
%
words(Words) => 
   Words= [[h, o, s, e, s], %%  HOSES
           [l, a, s, e, r], %%  LASER
           [s, a, i, l, s], %%  SAILS
           [s, h, e, e, t], %%  SHEET
           [s, t, e, e, r], %%  STEER
           [h, e, e, l],    %%  HEEL
           [h, i, k, e],    %%  HIKE
           [k, e, e, l],    %%  KEEL
           [k, n, o, t],    %%  KNOT
           [l, i, n, e],    %%  LINE
           [a, f, t],       %%  AFT
           [a, l, e],       %%  ALE
           [e, e, l],       %%  EEL
           [l, e, e],       %%  LEE
           [t, i, e]].     %%  TIE


%
% Overlappings of the words
% As an array for easy acces 
%
overlapping(Overlapping) => 
    Overlapping =
              [[1, 3, 2, 1], 
               [1, 5, 3, 1], 
             
               [4, 2, 2, 3], 
               [4, 3, 5, 1], 
               [4, 4, 3, 3], 
               
               [7, 1, 2, 4], 
               [7, 2, 5, 2], 
               [7, 3, 3, 4], 
               
               [8, 1, 6, 2], 
               [8, 3, 2, 5], 
               [8, 4, 5, 3], 
               [8, 5, 3, 5]].