15.9.1 Finite Domains

• Type hierarchies. Suppose you have a type hierarchy with types top, a, b, bot with an ordering relation satisfying

  top>a, top>b, a>bot, b>bot

  Encode types in Oz such that the representations of each two types are unifiable. The idea is that a type t can be represented by a finite domain constraint. For each type t we fix a fresh variable and represent t by the constraint where is the finite set .

• Grocery store. Solve the following problem such that the search tree remains as small as possible: A kid goes into a grocery store and buys four items. The cashier charges $7.11, the kid pays and is about to leave when the cashier calls the kid back, and says ``Hold on, I multiplied the four items instead of adding them; I'll try again; Hah, with adding them the price still comes to $7.11''. What were the prices of the four items?

• Morps, his kids, and the television This is a "Logelei" from the German newspaper Zeit from September 23, 1999 (thanks to Sebastian Pado for sending it to me.) Morps has a problem. His kids are watching televison the whole day over instead of doing their homework for school. But now, he has constructed a new TV and integrated into the network of the televison. At this TV, there are 7 switches A, B, C, D, E, F, G each of which an be brought into 4 positions. But only in a single of the 16384 possible combinations, the television can be switched on. This combination can be derived from the respective negations of the following 10 conditions.

  • A must be on 3 but D cannot.

  • A must not be on 4 but F has to be on 1.

  • B must not be on 1. If C is on 4 then F must be on 2.

  • A must be on 1 but not B on 3.

  • G mustn't be on 1, A has to be on 2 or 4.

  • Neither D on 1 nor B on 2.

  • Neither D on 2 nor G on 3.

  • B must be on 3 but G cannot be on 2.

  • G mustn't be on 2, and if E is on 2 then F must be on 3.

  • G must be 1 but A cannot be 1.

  Morphs puts this list of condition on top of TV. A kid that is intelligent enough to find the right combiniation will also be able to chose good TV shows only

• Choice. Write a binary procedure Choice by using an or-statement and FD.distribute. A call of {Choice P1 P2} shoud behave such as choice {P1} [] {P2} end.

• Placement. Suppose you are given retangle of size and a list of squares with dimensions . Find a placement of all squares within the rectangle such that no two squares overlap.

  

  Hints:

  • You can express the no-overlap constraint for each two small squares by a disjunction of arithmetic formulas. Let be the coordinates of square . The following constraint express that square and do not overlap:

    

    This disjunction for can either be expressed by a reified FD-constraints or else by an or-propagator with choice variables. Alternatively, you can use a global constraint FD.distinct2 for expressing all no-overlap constraints for all at once.

  • For each column and row you need a capacity constraint which ensure that not two many squares have to be placed on it.

  • It is important in which order you enumerate the finite domain variables: First place larger square and organize placement from left to right.

  Here comes a list of example instances of the problem:

  problems(
   unit(squares: [18 15 14 10 9 8 7 4 1] sx:32 sy:33)
   unit(squares: [3 2 2 1 1 1] sx:5 sy:4)
   unit(squares: [50 42 37 35 33 29 27 25 24 19
                  18 17 16 15 11 9 8 7 6 4 2] sx:112 sy:112)
   unit(squares: [9 8 8 7 5 4 4 4 4 4 3 3 3 2 2 1 1] sx:20 sy:20)
   unit(squares: [6 4 4 4 2 2 2 2] sx:10 sy:10)
   )

  Finally, here is a procedure that allows you to output the placement of squares graphically.

  declare 
proc {ShowTiles SX SY Squares Zoom}
   Color = red  
   Off=1
   W = {New Tk.toplevel tkInit}
   {Tk.send wm(resizable W 0 0)}
   {Tk.send wm(title(W "Tiling Problems"))}
   Canvas = {New Tk.canvas tkInit(parent:W
                                  width:SX*Zoom  
                                  height:SY*Zoom)}
in 
   {Tk.send pack(Canvas)}
   {ForAll Squares  
    proc{$ S}
       {Canvas tk(crea(rectangle S.x*Zoom+Off
                           S.y*Zoom+1  
                           (S.x+S.size)*Zoom+Off  
                          (S.y+S.size)*Zoom-Off
                          o(fill:Color)))}
    end}
end 
/*
 
declare  
Squares =  
   [square(size:3 x:0 y:0) square(size:2 x:3 y:2)  
    square(size:2 x:3 y:0) square(size:1 x:2 y:3)  
    square(size:1 x:1 y:3) square(size:1 x:0 y:3)]
{ShowTiles 5 4 Squares 40}
*/