/* 

  Rogo problem in Picat.

  From Mike Trick:
  "Operations Research, Sudoko, Rogo, and Puzzles"
  http://mat.tepper.cmu.edu/blog/?p=1302
  """
  [T]he goal is to find a loop through a grid of fixed length that contains 
  as many reward points as possible.
  """
  
  See: http://www.rogopuzzle.co.nz/

  Note: We don't assume that we have a best parameter
        (>0), to able to run the Rogo instances where we don't 
        know this value.

  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 => 
   time2(rogo(mike_trick)),
   nl.

% The hardest problem
go2 => 
   time2(rogo(intro8)), 
   nl.

% All problems
go3 => 
  Problems = [mike_trick, 20110106, 20110107, 20110709, 20110710, 
             20110711, 20110712, 20110713, 
             intro1, intro2, intro3, intro4, intro5, intro6, intro7, intro8],
  foreach(Problem in Problems)  
    time2(rogo(Problem)),
    nl
  end,
  nl.
  

rogo(PNr) =>

   println(problem=PNr),
   problem(PNr,Problem,MaxSteps,Best),
   % println(problem=Problem),

   % W = 0, % white empty cells
   B = -1, % black cells

   Rows = Problem.length, % 5.
   Cols = Problem[1].length, % 9,
   println([rows=Rows,cols=Cols,maxSteps=MaxSteps,best=Best]),
   
   % The valid connections (for table_in/2)
   Connections = [ {(I1-1)*Cols+J1,(I2-1)*Cols+J2} :
                    I1 in 1..Rows, J1 in 1..Cols, I2 in 1..Rows, J2 in 1..Cols,
                      ((abs(J1-J2) == 1, I1 == I2); 
                       (abs(I1-I2) == 1, J1 mod Cols == J2 mod Cols)
                       )
                 ],

   %
   % decision variables
   % 

   % coordinates in the path
   X = new_list(MaxSteps),
   X :: 1..Rows,
   Y = new_list(MaxSteps),
   Y :: 1..Cols,

   % coordinates as integers
   Path = new_list(MaxSteps),
   Path :: 1..Rows*Cols,


   % the collected points
   MaxPoint = max([Problem[I,J] : I in 1..Rows, J in 1..Cols]),
   MaxSum = sum([Problem[I,J] : I in 1..Rows, J in 1..Cols, Problem[I,J] > 0]),
   MaxBest = cond(Best > 0, Best, MaxSum),
   SumPoints :: 0..MaxBest,

   Points = new_list(MaxSteps),
   Points :: 0..MaxPoint,

   %
   % constraints
   %

   %
   % channel between path (integer representation) and 
   % the coordinate representation in (x, y)
   %
   foreach(I in 1..MaxSteps)
     Path[I] #= (X[I]-1)*Cols + Y[I]
   end,

   % all coordinates must be unique (first approach)
   % Note: Sometimes it's faster if this is also active.
   % foreach(S in 1..MaxSteps, T in S+1..MaxSteps)
   %    X[S] #!= X[T] #\/ Y[S] #!= Y[T]
   % end,

   % all coordinates must be unique
   % all_different(Path),
   all_distinct(Path),


   % check with best number of points
   if Best > 0 then 
      SumPoints #=< Best
      % SumPoints #= Best
   end,

   % calculate the points (to maximize)
   foreach(S in 1..MaxSteps) 
      % Points[S] #= Problem[X[S], Y[S]]
      matrix_element(Problem, X[S], Y[S], Points[S]),

      % ensure that there are no black cells
      % in the path
      Points[S] #!= B
   end,
   SumPoints #= sum(Points),

   % Get the path (coordinates)
   foreach(S in 1..MaxSteps-1)
      abs(X[S] - X[S+1]) + abs(Y[S] - Y[S+1]) #= 1
   end,
   % close the path around the corner
   abs(X[MaxSteps] - X[1]) + abs(Y[MaxSteps] - Y[1]) #= 1,

   %
   % Only valid connections, using table_in/2.
   %
   foreach(S in 1..MaxSteps-1) 
     table_in({Path[S], Path[S+1]}, Connections)
   end,
   % "around the corner"
   table_in({Path[1], Path[MaxSteps]}, Connections),

   %
   % Symmetry breaking 1: 
   % the cell with lowest coordinates should be in the first step.
   %
   foreach(I in 2..MaxSteps)
      Path[1] #< Path[I]
   end,


   % Symmetry breaking 2:
   % Second step should be larger than the first step
   Path[1] #< Path[2],

   %
   % Search
   % 

   Vars = Points ++ Path ++ X ++ Y ,

   solve($[max(SumPoints), degree,
             $report(printf("sumPoints=%w\npoints=%w\n     x=%w\n     y=%w\n  path=%w\n", SumPoints,Points,X,Y,Path))],
           Vars),
   nl,

   println(x=X),
   println(y=Y),
   println(path=Path),
   println(points=Points),
   println(sumPoints=SumPoints),

   nl.


% Data from
% Mike Trick: "Operations Research, Sudoko, Rogo, and Puzzles"
% http://mat.tepper.cmu.edu/blog/?p=1302
%
% LazyFD gives the following solution in 1.1 second:
%
% points = [0, 1, 0, 0, 2, 0, 0, 2, 0, 0, 3, 0]);
% sum_points = 8;
% x = [2, 2, 3, 4, 5, 5, 5, 4, 3, 3, 2, 2]);
% y = [4, 5, 5, 5, 5, 4, 3, 3, 3, 2, 2, 3]);
% 
% Which is correct, though not exactly the same as the 
% one at Mike Tricks blog post:
% Instead of turning from 4,3 -> 4,2 -> 3,2
% this takes              4,3 -> 3,3 -> 3,2
% 
% This has 48 solutions with symmetries;
% 4 when the path symmetry is removed.
%
problem(mike_trick, Problem, MaxSteps, Best) =>    
   W = 0,
   B = -1,
   Problem = [
     [2, W, W, W, W, W, W, W, W],
     [W, 3, W, W, 1, W, W, 2, W],
     [W, W, W, W, W, W, B, W, 2],
     [W, W, 2, B, W, W, W, W, W],
     [W, W, W, W, 2, W, W, 1, W]],
   MaxSteps = 12,
   Best = 8.


%
% Rogo problem from 2011-01-06
% 16 steps, good: 28, best: 31
%
problem(20110106, Problem, MaxSteps,Best) => 
  MaxSteps = 16,
  Best = 31,
  W = 0,
  B = -1,
  Problem =
[
  [B,W,6,W,W,3,B], % 1
  [2,W,3,W,W,6,W], % 2
  [6,W,W,2,W,W,2], % 3
  [W,3,W,W,B,B,B], % 4
  [W,W,W,2,W,2,B], % 5
  [W,W,W,3,W,W,W], % 6
  [6,W,6,B,W,W,3], % 7
  [3,W,W,W,W,W,6], % 8
  [B,2,W,6,W,2,B]  % 9
].


% The Rogo problem from 2011-01-07
problem(20110107, Problem,MaxSteps,Best) =>
  MaxSteps = 16,
  Best = 36,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7
  [4,7,W,W,W,W,3], % 1
  [W,W,W,W,3,W,4], % 2
  [W,W,4,W,7,W,W], % 3
  [7,W,3,W,W,W,W], % 4
  [B,B,B,W,3,W,W], % 5
  [B,B,W,7,W,W,7], % 6
  [B,B,W,W,W,4,B], % 7
  [B,4,4,W,W,W,B], % 8
  [B,W,W,W,W,3,B], % 9
  [W,W,3,W,4,B,B], % 0
  [3,W,W,W,W,B,B], % 1
  [7,W,7,4,B,B,B]  % 2
].


% The Rogo problem from 2011-07-09
problem(20110709, Problem, MaxSteps,Best) => 
  MaxSteps = 16,
  Best = 27,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,9,
  [B,2,7,W,B,W,5,3,B], % 1
  [W,W,W,W,3,W,W,W,W], % 2
  [W,W,B,3,W,W,2,W,W], % 3
  [W,W,W,W,3,W,W,W,W], % 4
  [B,2,5,W,B,W,5,5,B] % 5
].

% The Rogo problem from 2011-07-10
problem(20110710, Problem, MaxSteps, Best) => 
  MaxSteps = 20,
  Best = 55,
  W = 0, 
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,9,10
  [W,8,W,W,8,W,W,W,8,B], % 1
  [8,B,W,W,W,4,W,W,W,8], % 2
  [W,4,W,W,3,B,W,W,3,W], % 3
  [W,W,4,W,W,4,W,W,B,4], % 4
  [W,8,B,W,W,W,W,W,8,W], % 5
  [8,W,4,W,4,B,4,W,W,8] % 6
].


% The Rogo problem from 2011-07-11
problem(20110711, Problem, MaxSteps, Best) => 
  MaxSteps = 16,
  Best = 40,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,9,10
  [B,7,W,W,W,W,3,W,W,7], % 1
  [5,W,W,3,W,W,B,7,W,W], % 2
  [W,W,7,B,7,W,5,W,8,W], % 3
  [W,W,W,W,W,5,W,W,B,5], % 4
  [7,B,4,W,3,B,W,W,3,W], % 5
  [W,5,W,W,W,7,W,W,W,W] % 6
].

% The Rogo problem from 2011-07-12
problem(20110712, Problem, MaxSteps, Best) =>
  MaxSteps = 16,
  Best = 27,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,9,10
  [8,W,3,B,4,4,B,8,W,8], % 1
  [W,W,W,W,W,W,W,W,W,W], % 2
  [8,W,B,W,4,W,W,B,W,8], % 3
  [B,W,3,W,W,3,W,W,W,B], % 4
  [B,W,W,W,5,W,W,4,W,B], % 5
  [5,W,B,W,W,4,W,B,W,8], % 6
  [W,W,W,W,W,W,W,W,W,W], % 7
  [8,W,8,B,3,4,B,3,W,8] % 8
].


% The Rogo problem from 2011-07-13
problem(20110713,Problem,MaxSteps,Best) =>
  MaxSteps = 12,
  Best = 24,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,
  [7,W,W,W,2,W,4,W], % 1
  [7,B,W,W,W,B,5,2], % 2
  [W,W,2,W,4,W,W,W], % 3
  [W,W,W,W,2,W,W,5], % 4
  [2,W,W,B,W,5,W,W], % 5
  [W,W,2,W,B,W,W,4], % 6
  [4,W,W,4,W,W,W,W], % 7
  [W,W,W,2,W,W,W,W], % 8
  [2,5,B,W,W,W,B,5], % 9
  [W,4,W,2,W,W,W,7] % 10
].


% The Rogo problem Intro 1
% 
% http://www.rogopuzzle.co.nz/paper-rogos/intro-rogo-1/
%
problem(intro1, Problem, MaxSteps, Best) => 
  MaxSteps = 12,
  Best = 8,
  W = 0,
  B = -1,
  Problem = 
  [
 %1 2 3 4 5 6 7,8,9,
  [2,W,W,W,W,W,W,W,W], % 1
  [W,3,W,W,1,W,W,2,W], % 2
  [W,W,W,W,W,W,B,W,3], % 3
  [W,W,2,B,W,W,W,W,W], % 4
  [W,W,W,W,2,W,W,1,W] % 5
].

% The Rogo problem Intro 2
% 
% http://www.rogopuzzle.co.nz/paper-rogos/intro-rogo-2
%
problem(intro2, Problem, MaxSteps, Best) => 
  MaxSteps = 12,
  Best = 12,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,9,
  [W,W,B,W,4,W,W,W,W], % 1
  [W,W,1,W,W,W,1,W,W], % 2
  [4,W,W,W,3,W,W,W,2], % 3
  [W,W,2,W,W,W,1,W,W], % 4
  [W,W,W,W,1,W,B,W,W] % 5
].



% The Rogo problem Intro 3
% 
% http://www.rogopuzzle.co.nz/paper-rogos/intro-rogo-3/
%
problem(intro3, Problem, MaxSteps, Best) => 
  MaxSteps = 12,
  Best = 14,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,
  [2,W,3,W,1,W,W,2], % 1
  [W,3,W,W,W,W,4,W], % 2
  [4,W,1,W,W,4,W,1], % 3
  [W,W,B,2,2,B,W,W], % 4
  [W,W,2,W,W,2,W,W] % 5
].

% The Rogo problem Intro 4
% 
% http://www.rogopuzzle.co.nz/paper-rogos/intro-rogo-4
%
problem(intro4, Problem, MaxSteps, Best) => 
  MaxSteps = 12,
  Best = 21,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,9
  [5,W,W,W,B,W,W,W,5], % 
  [W,3,W,W,W,W,W,4,W], % 2
  [W,W,1,W,W,W,4,W,W], % 3
  [W,W,3,W,W,W,5,W,W], % 4
  [W,5,W,W,W,W,W,3,W], % 5
  [4,W,W,W,B,W,W,W,2] % 6
].

% The Rogo problem Intro 5
% 
% http://www.rogopuzzle.co.nz/paper-rogos/intro-rogo-5/
%
problem(intro5, Problem, MaxSteps, Best) => 
  MaxSteps = 16,
  Best = 21,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,
  [W,W,1,B,B,2,W,W], % 1
  [W,5,W,W,W,W,2,W], % 2
  [1,W,W,3,2,W,W,5], % 3
  [W,4,W,W,W,W,1,W], % 4
  [B,W,1,W,W,4,W,B] % 5

].


% The Rogo problem Intro 6
% 
% http://www.rogopuzzle.co.nz/paper-rogos/intro-rogo-6/
%
% Note: this problem has 16 optimal solutions.
% 
problem(intro6, Problem, MaxSteps, Best) => 
  MaxSteps = 16,
  Best = 43,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,9
  [W,W,5,2,4,1,W,W,W], % 1
  [W,4,W,B,W,W,7,W,W], % 2
  [2,W,W,W,7,W,6,W,5], % 3
  [1,4,W,3,W,W,W,6,B], % 4
  [B,B,7,W,W,3,W,1,B] % 5

].


% The Rogo problem Intro 7
% 
% http://www.rogopuzzle.co.nz/paper-rogos/intro-rogo-7/
%
problem(intro7, Problem, MaxSteps, Best) => 
  MaxSteps = 20,
  Best = 33,
  W = 0,
  B = -1,
  Problem = 
[
 %1 2 3 4 5 6 7,8,9
  [3,2,1,W,W,W,1,3,5], % 1
  [W,W,4,W,W,W,5,W,W], % 2
  [2,W,W,B,2,B,W,W,2], % 3
  [W,W,3,W,W,W,2,W,W], % 4
  [2,4,4,W,W,W,1,1,4] % 5

].



%
% The Rogo problem Intro 8
% 
% http://www.rogopuzzle.co.nz/paper-rogos/intro-rogo-8/
%
problem(intro8, Problem, MaxSteps, Best) =>
   W = 0,
   % B = -1,
   MaxSteps = 20,
   Best = 37, % 37
   Problem = [
  [5,4,W,W,3,W,1,W,3], % 1
  [W,W,W,4,W,W,3,W,W], % 2
  [W,1,W,W,W,W,5,4,4], % 3
  [3,W,3,W,W,3,W,W,W], % 4
  [W,W,W,W,W,W,W,W,W], % 5
  [W,W,W,5,W,W,3,W,W], % 6
  [4,W,3,3,W,4,1,W,4], % 7
  [W,5,W,W,W,W,W,3,W], % 8
  [5,W,W,W,W,3,W,W,W]  % 9
  ].