:-lib(ic). :-lib(branch_and_bound). stack(A,Z):- msort(A,B),supowit_i(B,[],YA), (twelve(T),\+((member(M,YA),length(M,L),L>T))->Z=YA; length(YA,YAL), length(A,AL),NL#::YAL..AL, % uncomment ONE of the next two lines % build_stacks(B,[],NL,Z)). bb_min(build_stacks(B,[],NL,YB),NL,YB,Z,_,_)). % general values of twelve twelve(12). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Supowit's algorithm % Generates a guaranteed minimal set of stacks, but without the restriction % to stack less than height 12. If the output happens to have fewer than 12 % height, this is optimal; and obviously no solution with the 12-height % limit can be better. % build up a solution by processing the boxes in sorted order by X supowit(A,Z):- msort(A,B), supowit_i(B,[],Z),!. % basis case - stop adding when there's nothing left to add supowit_i([],Z,Z). % add to highest chain we can supowit_i([box(PX,PY)|P],A,Z):- delete([box(BX,BY)|B],A,C), BY=BY)),!, supowit_i(P,[[box(PX,PY),box(BX,BY)|B]|C],Z). % start a new chain if we're forced to supowit_i([box(PX,PY)|P],A,Z):- supowit_i(P,[[box(PX,PY)]|A],Z). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % build_stacks(ToDo,Stacks,NumLists,Result) % ToDo - boxes still to add % Stacks - existing stacks % NumLists - constraint variable for number of lists % Result - final set of stacks % Basis case - nothing to add, we're done build_stacks([],Y,_NL,Y). % Recursive case - add to an existing stack build_stacks([box(AX,AY)|A],B,NL,Y):- twelve(T),length(A,AL),length(B,BL),NL#==L, build_stacks(AT,C,NL,Y). assign_keys([],[]). assign_keys([[box(AX,AY)|A]|B],[AY-[box(AX,AY)|A]|C]):-assign_keys(B,C).