Hi, I joined my solution that I made with the suggestion of Joachim Schimpf. To test it, I use the following command on random generated data (data.tar.gz) $ eclipse-clp -e "['stackingProblem.clp'],Ls=[`more data/data0.dbx`],stack(Ls,St),write(St),nl,halt." Also, like Thorsten Winterer suggested me, a more efficient approach would use classes of boxes where a class represent the set of boxes with the same dimensions. Benoît Hoessen 2010/3/18 Riyadh Abdulkadir <riyadhabdulkadir_at_gmail.com>: > 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® 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 > >> > > ------------------------------------------------------------------------------ > Download Intel® 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 > >
This archive was generated by hypermail 2.2.0 : Thu Feb 02 2012 - 02:31:58 CET