## CS23005 Design and analysis of algorithms | ## Autumn 2004--2005 |

**Theorem:** If we remove a square from a
2^{k}x2^{k} chessboard, the remaining part of
the board can be covered completely by non-overlapping L-shaped objects.
Here an L-shaped object consists of three squares. Four types of L-shaped
objects are given in the figure below.

*Proof.*
We proceed by induction on *k*. For *k*=1 the theorem is obvious.
So assume that the result holds for some value of *k*>=1 and we
are given a 2^{k+1}x2^{k+1} chessboard and a
square in it. (See the figure below.) We first divide
the board in four equal parts, each of size 2^{k}x2^{k}.
Assume that the given square is in the lower left part. Remove three
squares from the three other parts as shown in the figure. By induction
each part can now be covered by L-shaped objects. Finally, add an L-shaped
object covering the three squares removed near the center. QED

In this assignment you are supposed to compute an explicit covering of
a 2^{k}x2^{k} board minus a square. Write a
recursive procedure based on the idea given in the proof above. Make only
__two__ recursive calls for each value of *k*>1. Since the
three parts with squares removed from the corners are identical in
configuration (but differ only in orientation), a single recursive call
suffices for these three parts.

The squares in the board are numbered as described in the next figure. The numbering starts from zero at the lower left corner in both horizontal and vertical directions. Four types of L-shaped objects are also shown. An L-shaped object is identified by the number (i,j) of its central square and its type (an integer between 1 and 4).

For viewing the covering generated by your code, generate a PostScript file.
You don't have to learn how to write PostScript files. Follow the instructions
given below. Suppose that you want to generate the output file `chess.ps`.

- Copy the file
`preamble.ps`to`chess.ps`. - Append the line
dim D

Here`dim`is the (x or y) dimension of the chessboard (2^{k}). - Then for each L-shaped object generated by your code, add the line
i j LT

Here (i,j) are the row and column numbers of the central cell of the L-shaped object and`T`is the type of the L-shaped object. Follow the convention described in the figure above. - Let the initial square removed have the number (x,y). Add the line
x y H

to`chess.ps`. - Finally add the line
showpage

at the end of the output file.

`chess.ps` is now a complete PostScript file that can be viewed or printed.

An example for the case *k*=3 (the standard chessboard) is given below.
The (4,6)-th square is initially removed. Your program should generate
something like the following lines:

8 D 0 7 L1 3 7 L2 0 4 L3 2 5 L1 1 6 L1 5 7 L2 7 7 L2 4 4 L3 7 4 L4 6 5 L4 0 3 L1 2 2 L3 0 0 L3 3 0 L4 1 1 L3 5 2 L4 7 3 L2 4 0 L3 7 0 L4 6 1 L4 3 3 L3 4 6 H showpageHere is the complete file.

Submit the following files:

- The source code (
`chess.c`). - The output PostScript file for
*k*=5 or 6 (`chess.ps`).

srand((unsigned int)wxyz);Generate a random point to be removed from the board.