CS23005 Design and analysis of algorithms
Theorem: If we remove a square from a 2kx2k 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 2k+1x2k+1 chessboard and a square in it. (See the figure below.) We first divide the board in four equal parts, each of size 2kx2k. 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 2kx2k 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.
dim DHere dim is the (x or y) dimension of the chessboard (2k).
i j LTHere (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.
x y Hto chess.ps.
showpageat 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:
srand((unsigned int)wxyz);Generate a random point to be removed from the board.