CODEWITHSUNDEEP
constraintsconstraint-programmingmaximizeminizinc
Clara Marti
Clara Marti

Reputation: 41

Declare a variable to maximize it in Minizinc

I have a problem which is determine the maximum length of movements that a set of knights could make inside a board, which the conditions:

Here is my code, but I don't know how to modify the program to maximize the value of the path (t):

include "globals.mzn";

int: n=4; %nxnxt board
int: k=1; %k times visited cell
var 0..100: t; %Lenth of the path

%Initial board
array[1..t, 1..n, 1..n] of var 0..k:b;

% Decision variables (*CHANGED*)
array[1..t,1..4] of var 1..n: r;% The sequence of moves in the path
array[1..t,1..4] of var 1..n: c;% (row and column of each move).
%%% Always the same order A -> B -> C -> D knights

%Constraints

   % Forcing the first moves.

constraint r[1,1] = 1;%A
constraint c[1,1] = 1;
constraint r[1,2] = 1;%B
constraint c[1,2] = n;
constraint r[1,3] = n;%C
constraint c[1,3] = 1;
constraint r[1,4] = n;%D
constraint c[1,4] = n;

constraint b[1,1,2] = k;
constraint b[1,1,3] = k;
constraint b[1,2,1] = k;
constraint b[1,3,1] = k;
constraint b[1,2,4] = k;
constraint b[1,3,4] = k;
constraint b[1,4,2] = k;
constraint b[1,4,3] = k;

% LIMIT ON VISITS (*ADDED*)
constraint
     forall (i in 1..t, j in 1..n, l in 1..n) (
           b[i,j,l] <= k
     );

% SUCCESSOR (STEP OF THE KNIGHT)

constraint
     forall (i in 1..t-1, j in 1..4) (
           c[i,j] != c[i+1,j] /\%Each movement has to be diferent than the previous one
           r[i,j] != r[i+1,j] /\
           abs(c[i,j] - c[i+1,j]) + abs(r[i,j] - r[i+1,j]) = 3
     );
     
% NEVER TWO QUEENS ON THE SAME CELL

constraint forall(i in 1..t, j in 1..3, p in 2..4 where p > j )(
        r[i,j] != r[i,p] \/     
        c[i,j] != c[i,p]);
 
constraint forall(i in 2..t, j in 1..n, l in 1..n)(
      if b[i-1,j,l] = k then  
          b[i, j, l] = k
      endif
);

% APPLY THE MOVE IN THE MATRIX
constraint
     forall (i in 2..t, j in 1..4) ( 
         exists(w in {-2, 2}, q in {-1, 1}) ( % Set up the possible moviments.
         if  1 <= r[i-1,j]+w /\ r[i-1,j]+w <= n /\ 
             1 <= c[i-1,j]+q /\ c[i-1,j]+q <= n /\ 
             b[i-1, r[i-1, j]+w, c[i-1, j]+q] < k then
              (r[i,j] = r[i-1, j] + w /\
               c[i,j] = c[i-1, j] + q)
         endif
              \/
         if  1 <= r[i-1,j]+q /\ r[i-1,j]+q <= n /\ 
             1 <= c[i-1,j]+w /\ c[i-1,j]+w <= n /\ 
             b[i-1, r[i-1,j]+q, c[i-1,j]+w] < k then
              (r[i,j] = r[i-1, j] + q /\
               c[i,j] = c[i-1, j] + w) 
        endif) /\
        b[i, r[i,j], c[i,j]] = b[i-1, r[i,j], c[i,j]] + 1
);     
solve maximize t;

output["r"]++[
  if j = 1 then "\n" else "" endif ++
    show(r[i,j]) ++ " "
  | i in 1..t, j in 1..n   
]++["\n\nc"]++
[
  if j = 1 then "\n" else "" endif ++
    show(c[i,j]) ++ " "
  | i in 1..t, j in 1..n  
]++["\n"] ++
[ if l = 1 then "\n" else "" endif ++  
show(b[i,j,l]) ++ " " 
|i in 1..t, j in 1..n, l in 1..n];

include "globals.mzn";

int: n=4; %nxnxt board
int: k=1; %k times visited cell
var 0..100: t; %Lenth of the path
l in 1..n];

Upvotes: 0

Views: 188

Answers (1)

Zayenz
Zayenz

Reputation: 1964

A general approach in planning style problems is to first set an upper bound on the number of possible steps. Then the model is modified so that there is some sentinel no-move move that can be applied, but only at the end of the moves. Finally, you can count he number of moves used by counting the number of no-moves and subtracting that from the fixed upper bound.

Upvotes: 2

Related Questions