Homework 3

Due: Nov 1 2002 at 9:30am

Please email your solution to the TA, at courtney@apocalypse.com.

Problem 1: Tiling with Trominoes [35 pts]

Given a natural number n and a chess board with 2n squares on each side (the length of the side is 2n), you will first prove that 22n - 1 of the squares (that is, all but one) can be tiled by an arrangement of trominoes (an L-shaped arrangement of three squares; see figure below) such that all trominoes are confined to the boundaries of the chess board, and no tromino overlaps another. From this proof comes a recursive algorithm that you will then implement in Haskell.

a board,
with n=2 (2n=4)		 a tromino a tiling

It will be convenient to treat the origin (0,0) as the upper left corner of the board. Just for kicks, here is a larger tiling (with n=3):

1.1  The Proof [15 pts]

Prove, using induction, that the tiling is always possible. You will find that using pictures will help significantly in the proof. Reading the rest of this problem will also give you some significant hints on how to construct the proof.

Implementation

Now that you have a proof you should see a very easy recursive solution to generate a tiling. We will now implement that solution in Haskell. We will do it in parts to make it easier. It is very straight forward to implement the solution once the proof has been constructed, so it will definitely pay to do the proof first.

Orientation: We need a representation of the four possible orientations of a tromino. Notice how the tromino's shape resembles an "arrow." We will describe a tromino's orientation by using the direction in which the arrow points. The four possible directions are specified by the following datatype declaration: 

    data Orientation = NW | NE | SW | SE 
      deriving Show
The diagram below should make each orientation clear.
NW
northwest		 NE
northeast		 SW
southwest		 SE
southeast

Location: We also need to specify a tromino's location on the board. We will do so using the coordinate of the "arrow point square," expressed as a pair of points (x,y) with type (int, int). The board's upper-left square has a coordinate value of (0,0).

For computing the board size, 2n, I suggest you define a function pow2 :: Int -> Int. The infix power operator in Haskell is (**), but it returns a Float, so you will need to convert it back to an Int.

Tromino representation: Thus, a tromino can be represented by its orientation and a pair of points indicating the coordinate of its "arrow point square." Such a representation can be expressed with the following declaration: 

    type Tromino = (Int, Int, Orientation)
We can represent a tiling of the board with a list of trominoes. For example, the tiling seen at the beginning of this question can be represented by the following list: 
    [(0,0,NW),(3,0,NE),(3,3,SE),(0,3,SW),(1,1,NW)]

1.2  Translate [5 pts]

The first helper function to write is the translate function, which takes an (x,y) offset and a tromino list. The function shifts each of the given trominoes by the given offset, returning the resulting list of trominoes. 

    translate :: (Int,Int) -> [Tromino] -> [Tromino]
For example, if given the offset (2,3) and the list of trominoes [(1,1,SW),(3,3,NE)] and then translate should return [(3,4,SW),(5,6,NE)].

1.3  Flip [10 pts]

Next we need to be able to flip the board about either axis. We will call these functions xflip and yflip. They will take the length of one side of the board as its first argument, then the list of trominoes. Each function returns the reflected tromino list. 

    xflip :: Int -> [Tromino] -> [Tromino]
    yflip :: Int -> [Tromino] -> [Tromino]
The difference between them is illustrated in the following figure.

t0 xflip 4 t0 yflip 4 t0

1.4  Tile [5 pts]

You are almost there! To finish this problem, you just need to write the tile function, which takes an int n and tiles a square board with each side having length 2n. The tile function returns the list of trominoes needed to tile the board. The tiles need not be returned in any particular order. 
    tile :: Int -> [Tromino]

Problem 2: Rendering Trominoes [15 pts]

For this part of the assignment, you will use the Haskell graphics primitives to render a given tiling on the screen. (All of the graphics on this page are screen shots from Haskell!) At the top of your file you will have to import the graphics libraries: 
    import qualified SOEGraphics as G
Remember to use qualified names (such as G.xyz) to refer to functions in the library.

The top-level function, render, will take the title of the window, a natural number n, and a list of trominoes. It will open a window and render the trominoes in different colors. 

    render :: String -> Int -> [Trom] -> IO ()
First we must choose how many pixels to dedicate to each square of the board. I think 30 works well, but define this as a constant so it can be changed easily. 
    -- pixels per square
    pps = 30 :: Int
Here is a template for the render function: 
    render title n ts = G.runGraphics $
       do w <- G.openWindow title (dim,dim)
          ...other rendering operations...
       where dim = pow2 n * pps
We can use this to generate and render a tiling for a board of size 2n: 
    renderTiling :: Int -> IO ()
    renderTiling n = render ("tile "++show n) n (tile n)

You will probably find it useful to define an infinite stream of colors. The graphics library defines G.colorList :: [(Color,RGB)] where Color is a data type with constructors named Red, Blue, and so on. RGB is a triple of 8-bit words. The first color in the list is Black. Thus, the following code produces an infinite stream of all colors except for black. 

    colors = tail (map fst G.colorList) ++ colors
Feel free to substitute your own colors -- once your renderer is working!

I suggest rendering each tromino as a polygon. The library defines G.polygon :: [Point] -> Graphic for creating polygons from a list of points. Thus, the kernel of your program might be a function which generates polygon vertices for a given tromino: 

    trominoPolygon :: Tromino -> [Point]
You will probably want other helper functions, but the rest is up to you. Try to make your code as concise and elegant as possible.