Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I'm trying to model a puzzle in order to resolve it with the Choco solver.

One of the constraint I'm coding is cyclical (it's triplet which follow themselves) like the following example:

s.post(LogicalConstraintFactory.ifThen(
    IntConstraintFactory.member(mvt[i], new int[]{1, 2, 3}),
    IntConstraintFactory.not_member(mvt[i + 1], new int[]{1, 2, 3})
));
s.post(LogicalConstraintFactory.ifThen(
    IntConstraintFactory.member(mvt[i], new int[]{4, 5, 6}),
    IntConstraintFactory.not_member(mvt[i + 1], new int[]{4, 5, 6})
));
s.post(LogicalConstraintFactory.ifThen(
    IntConstraintFactory.member(mvt[i], new int[]{7, 8, 9}),
    IntConstraintFactory.not_member(mvt[i + 1], new int[]{7, 8, 9})
));
// and so one...

I think that my library isn't very known so the mathematics equivalent is :

if(foo[i] is in {1, 2, 3}) then
    foo[i+1] shouldn't be in {1, 2, 3}
if(foo[i] is in {4, 5, 6}) then
    foo[i+1] shouldn't be in {4, 5, 6}
...

Any idea of how I can model this problem with modulo (to avoid writing each triplet)?

share|improve this question
    
How consistent are your int values... is it always triples, and always starting from 1 (i.e. always [1,2,3],[4,5,6],[....],... ) –  rolfl Feb 15 at 15:47
    
@rolfl Yes, it's always triplet and starting from 1 –  Fractaliste Feb 15 at 15:50
add comment

3 Answers

up vote 4 down vote accepted

I'm not familiar with the choco solver, but would this solve your problem?

s.post(IntConstraintFactory.not_member(mvt[i+1], 
   new int[] { (mvt[i]/3)*3 + 1, (mvt[i]/3)*3 + 2, (mvt[i]/3)*3 + 3}));

Another option might be:

s.post(LogicalConstraintFactory.not(
  IntConstraintFactory.eucl_div(mvt[i+1]-1, 3, (int)(mvt[i]-1)/3)));

From the documentation:

/**
 * Ensures DIVIDEND / DIVISOR = RESULT, rounding towards 0 -- Euclidean division
 *
 * @param DIVIDEND dividend
 * @param DIVISOR  divisor
 * @param RESULT   result
 */
share|improve this answer
    
I like your idea, thanks a lot! –  Fractaliste Feb 15 at 16:52
add comment

If your triplets were zero-based (i.e., {0, 1, 2}, {3, 4, 5}, …) then the answer might have been more obvious. As it is, you have to apply an offset of -1, then divide by three to figure out which triplet an element belongs to.

if ((mvt[i] - 1) / 3 == (mvt[i + 1] - 1) / 3) {
    // This shouldn't happen: mvt[i] and mvt[i + 1] are in the same triplet
}
share|improve this answer
    
That's the sentiment that I want to express, but I see that mvt consists of IntVars, not ints, so you can't just perform ordinary arithmetic on them. However, I can't figure out how to express that using Choco solver constraints — and neither has anyone else so far. –  200_success Feb 15 at 17:26
    
You can consider IntVar as int, I'll perform by myself the arithmetic to choco library translation. Don't care about it. –  Fractaliste Feb 15 at 17:38
add comment

If the process is consistently 123, then 456, etc. and the check is always 'if a value is in one triplet, then the next value is not allowed in the same triplet, then you can have the following simple function:

int thisval = mvt[i];
// because thisval triplets are 1-based, you need to offset by -1 on the modulo
int excludemin = (thisval - ((thisval - 1) % 3));
int excludemax = excludemin + 3;
if (mvt[i+1] >= excludemin && mvt[i+1] < excludemax) {
    // this is not supposed to happen....
    // the i+1 element is inside the same triplet.
}

I am not sure how this would fit in your paradigm.... but, it is just one test for your whole system

share|improve this answer
    
The OP code says the next element can't be in the same triplet... –  Uri Agassi Feb 15 at 16:23
    
Duh.. fixed.. thanks –  rolfl Feb 15 at 16:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.