Drawing a Chess Board or How Generalizing Simplifies

Matthias Felleisen

Pedagogic Goal: to illustrate how generalizing a problem makes it easier to solve it.

Content Goal: to draw a chess board on a canvas

Background: A chess board is a square of 8 times 8 fields in two colors:

To discuss a square on the board, we need to agree on how to count rows and columns. We use natural numbers to do so, and thus speak of rows 0, 1, 2, 3, ... and similarly of column 0, 1, 2, etc. Using this agreement, we can refer to a square with a pair of numbers: its column and its row. For example, the square to the right of the top-most, left-most corner is located at (1, 0). The third square 3 rows down from the corner is (0,3). Here is a picture that shows just these two squares:

Pick a few other squares on a board and determine their positions. Conversely, pick some positions and show to which square they correspond.

Exercises

Exercise 1: Develop the function color. The function consumes the column and the row of a square and produces its color. Hint: Define the constants WHITE and BLACK, representing the two colors as symbols. Prerequistes: HtDP 5.1

Exercise 2: Develop the function draw-square. It consumes the column and the row of a square and draws it on a canvas. Hint: Define the constant SQUARE, which specifies the width and height of a single square. Then define the constant WIDTH in terms of SQUARE for an 8 x 8 board. Don't forget to use (start WIDTH WIDTH) for testing draw-square. Prerequistes: HtDP 6.2

Exercise 3: Develop the function draw-column. The function consumes a column index and draws one column of an 8 x 8 chess board on a canvas. Here are two examples:

The picture on the left shows what drawing row 1 means, and the picture on the right shows what drawing rows 0 through 2 means. Prerequistes: HtDP 6.2

Solution: chess.ss contains the solutions for exercises 1 through 3.

Exercise 4: Develop a program that draws an 8 x 8 chess board using the solutions for the proceedings exercises. You may only add a single expression to the solutions. Prerequistes: HtDP 6.2

Solution: chess0.ss contains the solution for exercise 4.

The following two exercises show how generalizing the problem to drawing a chess board or arbitrary size actually simplifies the solution.

Exercise 5: Generalize the function draw-column so that it consumes the column index and the (natural) number of squares it is supposed to draw. Prerequistes: HtDP 11.3

Exercise 6: Develop the function draw-board. The function consumes two natural numbers, N and M, and draws a chess board with N columns, each with M squares.

Using draw-board, draw an 8 x 8 chess board. Prerequistes: HtDP 17 (or 11.3, plus a hint that this is case 1)

Solution: chess1.ss contains the solutions for exercises 5 and 6.

The following two exercises illustrate how using higher-order functions reduces the solution to a three-line function definition. It is important to remember that we can enumerate a desired series of indices using build-list and identity. For example, if we wish to work with the numbers 0 through 9, we just build a list of those numbers with

  > (build-list 10 identity)
  (list 0 1 2 3 4 5 6 7 8 9)

  > (apply + (build-list 10 identity))
  45

  > (for-each (lambda (i) (printf "~s " i)) (build-list 10 identity))
  ...

Exercise 7: Re-define the function draw-board using andmap and build-list. Prerequistes: HtDP 21.2

Solution: chess2.ss contains the solution for exercise 7.

Exercise 8: Use lambda to simplify draw-board even more. Prerequistes: HtDP Intermezzo 4

Solution: chess3.ss contains the solution for exercise 8.