I am modelling a constraint satisfaction program in minizinc where the solution is an assignment of points on a 3D grid. One of the constraints is that only one point can occupy any given position, so the points must be pairwise different in at least one of their coordinates.
My point variables are modelled as an N X 3 array of coordinates:
array[1..N,1..3] of var -N..N: X;
And the difference constraint is
constraint forall(i in 1..N-1)(forall(j in i+1..N)(not X_eq(i,j))); %extremely slow
predicate X_eq(int: a, int: b)=
(X[a,1]=X[b,1]/\X[a,2]=X[b,2]/\X[a,3]=X[b,3]);
But the solution time for the problem skyrockets when I formulate the constraint like this. I have many other constraints to be added and its already way to slow to just find points that are different.
I tried to instead model the points as
array[1..N] var set of -N..N
So that I could use the built-in function
all_different
But then I see how to enforce sets to have cardinality 3, and also it seems less natural to use the generic sized sets to model a triplet of ints.
My question is: What is a tractable and 'correct' way to model a coordinate set and the all-different constraint?
I am using the gecode solver that comes in the minizinc IDE bundle. The model is shown below. Solution time is 24 minutes.
array[1..N] of 0..1: seq=[1,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,1,0];
int: N=18;
int: H=6;
array[1..N,1..3] of var -N..N: X;
array [1..H,1..3] of 0..N:c;
%H are in core
constraint forall(i in 1..N)( if (seq[i]=1) then exists(j in 1..H)([i,1]=c[j,1] /\ X[i,2]=c[j,2] /\ X[i,3]=c[j,3] ) else true endif);
%All points different
constraint forall(i in 1..N-1)(forall(j in i+1..N)(not X_eq(i,j))); %extremely slow
predicate X_eq(int: a, int: b)=
(X[a,1]=X[b,1]/\X[a,2]=X[b,2]/\X[a,3]=X[b,3]);
solve satisfy;
output[show(X[i,j]) ++ " "|i in 1..N,j in 1..3]++["\n"];
c=[|0,0,0|
0,0,1|
0,0,2|
0,1,0|
0,1,1|
0,1,2|];
Note: I ran your model as got the first solution in 60ms (not 24 minutes), using Gecode and the latest MiniZinc version from Git. So the stuff below might not help you...
Also, I answer your original problem, i.e. how to use all_different with the 3D array X (array[1..N, 1..3]). I might have missed something in your model, but here is a model that solves the satisfiability problem in 9ms.
The idea to create an array that converts a point to an integer: (X[I,1]-1)*N*N + (X[I,2]-1)*N + X[I,3] (cf the decimal number 523 is 5*10*10 + 2*10 + 3). Perhaps this must be adjusted, but you get the general idea. Also, I added - in a comment - another approach that compares each pairs of points that should be faster than your X_eq predicate.
Note that this all_different approach might be bad if the generated integers will be very large (e.g. for large N).
include "globals.mzn";
array[1..N] of 0..1: seq=[1,1,0,0,0,0,0,1,1,0,0,0,1,0,0,0,1,0];
int: N=18;
int: H=6;
array [1..H,1..3] of 0..N:c;
array[1..N,1..3] of var -N..N: X;
solve satisfy;
% hakank: here's my approach of all_different
constraint
all_different([(X[i,1]-1)*N*N + (X[i,2]-1)*N + X[i,3] | i in 1..N])
%% another approach (slower than all_different)
%% for each pair: ensure that there is at least one coordinate differ
% forall(I in 1..N, J in 1..N where I < J) (
% sum([X[I,K] != X[J,K] | K in 1..3]) > 0
% )
;
% from original model
constraint
%H are in core
forall(i in 1..N)(
if (seq[i]=1) then exists(j in 1..H) (
X[i,1]=c[j,1] /\ X[i,2]=c[j,2] /\ X[i,3]=c[j,3]
)
else true endif
)
;
output
[
show([X[I,J] | J in 1..3]) ++ "\n"
| I in 1..N
]
;
c=[|0,0,0|
0,0,1|
0,0,2|
0,1,0|
0,1,1|
0,1,2|];