/* 

  Arrows puzzle in Picat.

  Problem from Jacques Pitrat: "Artificial Beings", 
  Appendix 1, page 244:
  """
  The goal is to put an integer in each square so that the number of different
  values in the squares pointed to by this arrow is equal to this integer.
  These problems are usually difficult, this is due to their reflexive nature:
  a value V depends on the other values, which depend on V!
  """
  
    > ^ < < v > ^
    > > ^ ^ > > > 
    < ^ < ^ v > >
    > v < > > > ^
    > < ^ ^ > < > 
    > ^ < ^ > > v

  which is coded as
    ^:    up     (1)
    >: -> right  (2)
    v:    down   (3)
    <: <- left   (4)


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

*/


import util.
import cp.

main => go.


go =>
  problem(mal1,Problem),
  time2(arrows(Problem,_X1)),

  problem(mal33,Problem33),
  time2(arrows(Problem33,_X33)),

  nl.

go2 =>

  problem(mal33,Problem33),
  time2(All=findall(_,arrows(Problem33,_X33))),
  println(num_solutions=All.length),

  nl.


arrows(Problem, X) =>

  Rows = Problem.length,
  Cols = Problem[1].length,

  Up = 1,
  Right = 2,
  Down = 3,
  Left = 4,

  X = new_array(Rows,Cols),
  X :: 0..max(Rows,Cols),

  foreach(I in 1..Rows, J in 1..Cols) 

     if Problem[I,J] = Left then
        Tmp = [X[I,B] : B in 1..J-1]
     elseif Problem[I,J] = Right then
        Tmp = [X[I,B] : B in J+1..Cols]
     elseif Problem[I,J] = Up then
        Tmp = [X[A,J] : A in 1..I-1]
     elseif Problem[I,J] = Down then
        Tmp = [X[A,J] : A in I+1..Rows]
     else 
        println("Something is weird. Direction should be Left, Right, Up, or Down")
     end,

     % println([I,J,Tmp]),
     nvalue(X[I,J], Tmp)

  end,

  % solve([degree],X), % solves mal33 (first solution) in 0.51s 2285 backtracks

  solve([split,forward],X), % solves mal33 (first solution) in 0.27s 0 backtracks
  % solve([split],X),

  foreach(Row in X) println(Row) end,

  nl.


/*
%
% nvalue(?N,?X)
%
% Requires that the number of distinct values in X is N.
%
nvalue(N,[])  => N = 0.
nvalue(N, X) =>
   Len = length(X),
   LB = min([fd_min(X[I]) : I in 1..Len]),
   UB = max([fd_max(X[I]) : I in 1..Len]),
   N #= sum([ sum([ X[J] #= I : J in 1..Len]) #> 0 : I in LB..UB]).
*/

% 
% Problems from MALICE manual ("How to use MALICE")
% """
% M indicates the number of columns, and N the number of lines. 
% Vector H indicates the orientation of the arrows, beginning by the bottom 
% line and going from left to right. 
%   1 is for an arrow towards the top, 
%   2 to the right, 
%   3 to the bottom , and 
%   4 to the left.
% """
% The problem MAL1 is coded as
%   M: 7
%   N: 6
%   H
%   2,1,4,1,2,2,3, (last row)
%   2,4,1,1,2,4,2,
%   2,3,4,2,2,2,1,
%   4,1,4,1,3,2,2,
%   2,2,1,1,2,2,2,
%   2,1,4,4,3,2,1  (first row)
%
problem(mal1,Problem) =>
Problem = 
[
  [2,1,4,4,3,2,1], % 1 (first row)
  [2,2,1,1,2,2,2], % 2
  [4,1,4,1,3,2,2], % 3
  [2,3,4,2,2,2,1], % 4
  [2,4,1,1,2,4,2], % 5 
  [2,1,4,1,2,2,3]  % 6(last row)
].



%
% MAL33 (from the MALICE collection)
%
% MALICE give 8 solutions in 12 seconds using the "intelligent method"
% """
% I USED MY EFFICIENT METHOD, I FOUND 8 SOLUTIONS IN 12 SECONDS FOR THE 
% &ARROWS MAL33 PROBLEM, AND I DEVELOPED A TREE WITH 924 LEAVES.
% """
% MALICE give 8 solution in <1s using the intelligent/combinatorial method:
% """
% I USED THE COMBINATORIAL METHOD AFTER AN INTELLIGENT BEGINNING, I FOUND 8 
% SOLUTIONS IN 1 SECOND FOR THE &ARROWS MAL33 PROBLEM, AND I DEVELOPED A 
% TREE WITH 19 MILLION LEAVES.
% """
%
problem(mal33,Problem) =>
Problem= 
[
[2,4,2,4,3,3,2], % 1 first row
[2,4,3,3,3,4,1], % 2
[2,1,3,2,3,1,4], % 3
[2,2,2,1,4,4,1], % 4
[2,2,1,3,2,4,1], % 5
[2,4,1,4,3,4,3], % 6
[1,1,3,4,4,4,2] % 7 last row 
].