Re: [eclipse-clp-users] constraint on indexed elements

Hi everyone,

I found this problem interesting and here is my beginners solution. I
think that the createstacks/2 clause in particular can be improved. Has
anyone else given this a go?

% Start of program

% Program to arrange boxes in stacks of 12 depending on their width and depth
% A box can be stacked onto another box if the width and depth are
smaller or equal to the box below
% Only the minimum number of stacks required is checked, if no valid
solution is found it does not add more stacks
% A version with only 8 boxes and maximum stack of three boxes finds a
solution in a short time
% This version finds a solution quickly, you can rearrange the boxes
to make it more difficult

:-lib(ic).
:-lib(lists).

%list of 30 boxes
%argument 1 = box number, argument 2 = width, argument 3 = height

box(15, 31, 31).
box(16, 30, 30).
box(17, 29, 29).
box(18, 28, 28).
box(19, 27, 27).
box(20, 26, 26).
box(21, 25, 25).
box(22, 24, 24).
box(23, 23, 23).
box(24, 22, 22).
box(25, 21, 21).
box(26, 20, 20).
box(27, 19, 19).
box(28, 18, 18).
box(29, 17, 17).
box(30, 16, 16).
box(01, 15, 15).
box(02, 14, 14).
box(03, 13, 13).
box(04, 12, 12).
box(05, 10, 10).
box(06, 9, 9).
box(07, 8, 8).
box(08, 7, 7).
box(09, 6, 6).
box(10, 5, 5).
box(11, 4, 4).
box(12, 3, 3).
box(13, 2, 2).
box(14, 1, 1).

% clause to insert an element into a list - required by permutation clause

insert(X, L, L1) :-
	delete(X, L1, L).

% creates permutations of a list of items

permutation([], []).
permutation([X|L], P) :-
	permutation(L, L1),
	insert(X, L1, P).

% Attempts to add a box to the next box on the list
% Argument 1 is the stack of boxes to be added succesively
% Argument 2 is the box at the botton of the stack
% The checkpositions clause sends the first element of the stack as
the second clause and the rest of % the stack as the first clause

addbox([], _).
addbox([H|T], Boxstack) :-
	[S|_] = Boxstack,
	box(H, W1, _),
	box(S, W2, _),
	box(H, _, D1),
	box(S, _, D2),
	W1 =< W2,
	D1 =< D2,
	addbox(T, [H|Boxstack]).

% Divides the permutation of the list of boxes into stacks of 12
% The first predicate matches the last stack if it has less than 12 boxes
% It seems possible to code this in a better way

createstacks(Stack, Stack) :-
	length(Stack, N),
	N < 12,
	N > 0.
createstacks([B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12|_],
[B1, B2, B3, B4, B5, B6, B7, B8, B9, B10, B11, B12]).
createstacks([_, _, _, _, _, _, _, _, _, _, _, _|Rest], Stack) :-
	createstacks(Rest, Stack).

% Calls addbox for each stack

checkpositions([]) :- true.
checkpositions([[Sh|St]|T]) :-
	addbox(St, [Sh]),
	checkpositions(T).	

% The stackem clause uses findall to get a list of boxes
% I them calls permutation to get the first permutaion
% The second findall createstacks to create a list of all stacks
% Finally is calls checkpositions to check if each stack is valid


stackem(Boxes, Stacks) :-
	findall(B, box(B, _, _), Boxes),
	permutation(Boxes, OrderedBoxes),
	findall(Stack, createstacks(OrderedBoxes, Stack), Stacks),
	writeln(Stacks),
	checkpositions(Stacks).
	
% End of program		
		
	

Regards
Riyadh


On Thu, 2010-03-04 at 10:41 +1100, Joachim Schimpf wrote:
> Benoit Hoessen wrote:
> > Hello,
> >
> > First, thank you for your response. I will try to explain better the
> > problem I'm trying to solve and the problem I'm facing to model it
> > using ECLiPSe. My problem is the following: we have a list of N boxes
> > of different sizes but same height. We must create J stacks with those
> > boxes. A stack may contain up to 12 boxes. In a stack, the box B can
> > be put on box A if the width of A is greater or equals the width of B
> > and if the length of A is also greater or equals the length of B.
> >
> > My problem is that I don't know how I can model this.
> >
> > I tried to following way, but I don't think it's a good way to model it.
> > Data:
> > * A box is represented with a term: box(Length,Width). The N boxes are
> > in a list.
> > * A number is associated with the boxes by using a dynamic predicate
> > (boxIndex(+I, +B) : is true if B is a box and I is a number) where one
> > box is associated with 1 and only 1 number.
> > * The J stacks are represented by a list LStacks of length J
> > * A stack is represented by a list of length 12
> > * A box in a stack is represented by it's number
> > Constraints:
> > * To model the constraint "up to 12 boxes in a stack", J*12 - N boxes
> > of width=length=0 are created. The constraint is now that there will
> > always be 12 boxes in a stack
> >
> > My problem is to model the constraint on 2 boxes in a stack. I could
> > use the suspend library to wait that the 2 variables are instantiated
> > to check the satisfaction on the constraint, but I don't like this
> > approach as it won't use any domain consistency method.
>
> You can build this kind of constraint yourself with lib(propia):
>
> :- lib(ic).
> :- lib(propia).
>
> box_smallereq(I, J) :-
> 	box_index(I, box(WI, LI)) infers ic,
> 	box_index(J, box(WJ, LJ)) infers ic,
> 	WI #=< WJ,
> 	LI #=< LJ.
>
> box_index(1, box(5,4)).
> box_index(2, box(5,2)).
> box_index(3, box(7,3)).
> box_index(4, box(3,3)).
>
> Example:
> ?- box_smallereq(I, J), I #=< 2.
> I = I{[1, 2]}
> J = J{1 .. 3}
> There are 3 delayed goals.
> Yes (0.00s cpu)
>
>
> >
> > For me, in a "ideal world" I would'n use the number associated with
> > the boxes and the stacks would be represented by variables defined on
> > a domain D such that it is the set of the possible boxes. The
> > constraint on 2 boxes would be a kind of primitive constraint and as
> > it uses only 2 variable, an arc-consistency method could be used.
> > The problem is that -as far as I know- symbolic domains in ECLiPSe
> > don't accept terms.
>
> The ordering constraint is of course easy in this model:
>
> box_smallereq1(box(WI, LI), box(WJ, LJ)) :-
> 	WI #=< WJ,
> 	LI #=< LJ.
>
> but the problem is then to label the positions in the stacks with a
> permutation of the available boxes.  I haven't thought about it in
> detail, but you could probably use a model where you have variables
> that indicate in which stack a particular box is, and use sorted/3
> constraints to make sure the stacks are valid.
>
>
> >
> > Is there a way to get closer to my "ideal world" ?
>
> I think this is a very nice little problem!  I would be interested
> to hear suggestions from other users - we could even have a competition
> (unless, of course, this is your homework...)
>
>
> Cheers,
> -- Joachim
>
> ------------------------------------------------------------------------------
> Download Intel&#174; Parallel Studio Eval
> Try the new software tools for yourself. Speed compiling, find bugs
> proactively, and fine-tune applications for parallel performance.
> See why Intel Parallel Studio got high marks during beta.
> http://p.sf.net/sfu/intel-sw-dev
> _______________________________________________
> ECLiPSe-CLP-Users mailing list
> ECLiPSe-CLP-Users_at_lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/eclipse-clp-users
>