/*

  Futoshiki problem in Picat.
 
  http://en.wikipedia.org/wiki/Futoshiki
  """
  The puzzle is played on a square grid, such as 5 x 5. The objective
  is to place the numbers 1 to 5 (or whatever the dimensions are) such 
  that each row, and column contains each of the digits 1 to 5. Some 
  digits may be given at the start. In addition, inequality
  constraints are also initially specifed between some of the squares, 
  such that one must be higher or lower than its neighbour. These 
  constraints must be honoured as the grid is filled out.
  """

 

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

*/

import util.
import cp.

main => go.

go =>
   foreach(I in 1..3) 
      _ = findall(_,$futoshiki(I))
   end .

futoshiki(P) =>
   
   writef("\nProblem %d\n",P),
   problem(P,Problem,LessThans),

   N = Problem.length,
   X = new_array(N,N),
   X :: 1..N,

   % Fill the data
   foreach(I in 1..N, J in 1..N)
      if Problem[I,J] > 0 then
         X[I,J] #= Problem[I,J]
      end
   end,

   % constraints
   latin_square(X),
   foreach([I1,J1,I2,J2] in LessThans) X[I1,J1] #< X[I2,J2] end,

   % search
   solve(X),

   % output
   foreach(Row in X) println(Row.to_list()) end,
   nl.

latin_square(Board) =>
   foreach(Row in Board) all_different(Row) end,
   foreach(Column in Board.columns()) all_different(Column) end.


% Example from Tailor model futoshiki.param/futoshiki.param
%
% Solution:
% 5 1 3 2 4
% 1 4 2 5 3
% 2 3 1 4 5
% 3 5 4 1 2
% 4 2 5 3 1
% 
% Futoshiki instance, by Andras Salamon
%
problem(1, Problem, LessThan) =>
Problem =
   [[0,0,3,2,0],  % problem grid
    [0,0,0,0,0],
    [0,0,0,0,0],
    [0,0,0,0,0],
    [0,0,0,0,0]],

LessThan = 
   [[1,2,1,1], % [i1,j1, i2,j2] requires that values[i1,j1] < values[i2,j2]
    [1,4,1,5],
    [2,3,1,3],
    [3,3,2,3],
    [3,4,2,4],
    [2,5,3,5],
    [3,2,4,2],
    [4,4,4,3],
    [5,2,5,1],
    [5,4,5,3],
    [5,5,4,5]].


% Example from http://en.wikipedia.org/wiki/Futoshiki
% Solution:
% 5 4 3 2 1
% 4 3 1 5 2
% 2 1 4 3 5
% 3 5 2 1 4
% 1 2 5 4 3
%
problem(2, Problem, LessThan) =>
Problem =
   [[0,0,0,0,0],
    [4,0,0,0,2],
    [0,0,4,0,0],
    [0,0,0,0,4],
    [0,0,0,0,0]],
LessThan =
   [[1,2, 1,1],
    [1,4, 1,3],
    [1,5, 1,4],
    [4,4, 4,5],
    [5,1, 5,2],
    [5,2, 5,3]].


% From http://www.sudoku-puzzles.net/futoshiki06x6.html
problem(3, Problem, LessThan) =>
Problem = 
   [[5,0,2,0,1,0],
    [6,0,1,0,0,0],
    [0,0,3,0,0,0],
    [0,0,4,0,0,0],
    [0,0,0,4,2,5],
    [0,0,0,1,3,0]],
LessThan = 
   [[1,6, 2,6],
    [4,1, 3,1]].