Making reference to tuples within a constraint

[Filip Konvička]

Hi Michal,

>     /*    FIXME
>
>         {For 1 NUM-1 1 proc {$ I}
>
>             % The trailing edge of a placed match is the same the 
> leading edge
>             % of the next match.
>             M.(Pos.I).(2 - Flip.I) =: M.(Pos.(I+1)).(1 + Flip.(I+1))
>
>         end}
>
>     */   
I suppose that the statement(equation) in the for-loop is what you think 
should hold when a solution is found. (I did not analyze the this 
equation however...) But what should this statement do when the solution 
is under construction, i.e. when the variables "Pos.I", "Flip.I" etc. 
are not numbers, but (e.g.) intervals? Clearly, in such situation, the 
equation does not have sense, and so can not help in constructing the 
solution (so the solver ends up trying many solutions because of no 
propagation).

Technically, you should understand that the constraint-posting statement 
"A =: B" translates internally to
  {FD.sumC [1 ~1] [A B] '=:' 0}
i.e. a procedure call (see docs for FD.sumC) with some arguments which 
have to be passed to it (they can be non-determined FDInt variables). 
The problem in your case is that neither "A" or "B" can be evaluated at 
the point when FD.sumC is called (e.g. "M.(Pos.I)" is trying to access 
feature "Pos.I" of "M", but "Pos.I" is undetermined, so the expression 
blocks). The advice here is to rework your model to avoid the need for 
such constraints.

To be a bit more constructive, here is a hack that gets you a quick and 
dirty solution (I only changed the for loop and the last statement):
local
   %% Our matches, where each match has different coloured ends.
   %% Different colours represented by different numbers.
   %% Note that the matches are given in an order that provides a solution:
   %%    0---1 1---0 0---2 2---2 2---0  
   %%
   %% This is equavalent to the solution (see code):
   %%    solution(flip:flip(0 0 0 0 0) pos:pos(1 2 3 4 5))
   %%
   %% Another solution might be:
   %%    1---0 0---2 2---2 2---0 0---1
   %%
   %% This is equavalent to the solution (see code):
   %%    solution(flip:flip(1 1 0 0 0) pos:pos(1 5 2 3 4))
   %%
   NUM = 5
   M = matches(
          match(0 1)
          match(1 0)
          match(0 2)
          match(2 2)
          match(2 0)
          )
   proc {Solve Root}
        % Which numbered match is in each position of the line.
      Pos = {MakeTuple pos NUM}
        % Whether we rotated the match or not
      Flip = {MakeTuple flip NUM}
   in
      %% Post the solution
      Root = solution(pos:Pos flip:Flip)
      %% Initialize the variable domains.
      Pos = {FD.tuple pos NUM 1#NUM}
      Flip = {FD.tuple flip NUM 0#1}
      for I in 1..NUM-1 do
         %% The trailing edge of a placed match is the same the leading edge
         %% of the next match.
         thread
            M.(Pos.I).(2 - Flip.I) =: M.(Pos.(I+1)).(1 + Flip.(I+1))
         end
      end
      %% We can only place each match once.
      {FD.distinct Pos}
      {FD.distribute ff Pos}
      {FD.distribute ff Flip}
   end  
in
   {ExploreAll Solve}
end

(Note how I use "%%" instead of "%" to prevent indentation problems in 
emacs.) The thing that makes the difference is that the blocking 
statements "A =: B" run in separate threads and wait for all the needed 
variables to get determined (which happens during the FD.distribute 
calls). So you have a working example of the "generate-and-test" 
paradigm, which is not constraint programming (no constraint propagation 
takes place here). See the explorer tree - there are 720 failures and 40 
solutions. With good constraint propagation, you could perhaps avoid 
failures at all.

Cheers,
Filip