% attempt Supowit stack(A,Z):- supowit(A,Z),twelve(T),\+((member(M,Z),length(M,L),L>T)). % make the driver complain if Supowit failed stack(_,[[box(1,1),box(2,2)]]). % 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).