title: How to recursively tile a defective chessboard in DrRacket
body: <p>I have a homework problem which is really messing with me right now, and I could use some help in how to implement it in DrRacket. I do not wish for code, just guidance, as I am very new to DrRacket.</p>
  
  <p>The assignment is to implement this phrase:</p>
  
  <p><em>"If n = 0, return the empty tiling (list of tile structs). Otherwise, place a tromino (L-shaped domino) in the center of the chessboard so that it covers the three quadrants of the chessboard that have no missing tile in them, and tile each of the quadrants."</em></p>
  
  <p>as recursive code using the two .rkt files given. We are permitted to use any of the functions found within tromino.rkt.</p>
  
  <p>We are also told that the following functions will be necessary to write our code, and so I have included a description of what each does: </p>
  
  <p><strong>(center-tile n row column)</strong><br>
  This function produces a single tile structure that represents a properly oriented tromino placed at the center of a 2<sup>n</sup> × 2<sup>n</sup> chessboard when the chessboard has its missing tile in the specified row and column. Remember that rows and columns are numbered starting at zero. This function does quite a bit of work for you: It figures out which quadrant the missing cell is in, determines the proper orientation of the tromino to be placed at the center of the board so that that quadrant is not covered, and returns a tile structure that represents that tromino in the proper position on the board.</p>
  
  <p><strong>(missing-cell-within-quadrant n row column quadrant-row quadrant-column)</strong><br>
  The 2<sup>n</sup> × 2<sup>n</sup> chessboard is divided into four quadrants that are indexed just as the rows and columns are. Specifically, the upper-left quadrant corresponds to
  (quadrant-row, quadrant-column) set to (0, 0). The other quadrants are (0, 1) for upper right, (1, 0) for lower-left, and (1, 1) for lower-right. The function missing-cell-within-quadrant answers the following question:  </p>
  
  <p><em>What are the (row, column) coordinates within quadrant (quadrant-row, quadrant-column) of the missing or covered cell within that quadrant, after the tile produced by center-tile has been placed?</em>  </p>
  
  <p>The answer is in the form of a list with two coordinates, expressed in the frame of reference of each quadrant. For instance if the missing cell in a 2<sup>3</sup> × 2<sup>3</sup> board is at row 2, column 5, then after placement of the center tile the four calls</p>
  
  <p>(missing-cell-within-quadrant 3 2 5 0 0)<br>
  (missing-cell-within-quadrant 3 2 5 0 1)<br>
  (missing-cell-within-quadrant 3 2 5 1 0)<br>
  (missing-cell-within-quadrant 3 2 5 1 1)  </p>
  
  <p>return the following four lists, respectively:  </p>
  
  <p>'(3 3)<br>
  '(2 1)<br>
  '(0 3)<br>
  '(0 0)</p>
  
  <p><strong>(upgrade-tiling tiling m quadrant-row quadrant-column)</strong><br>
  Given a tiling — that is, a list of tromino tiles — of one of the four 2<sup>m</sup> × 2<sup>m</sup> quadrants of a 2<sup>n</sup> × 2<sup>n</sup> chessboard, where <strong>m = n−1</strong>, this function transforms all the tiles in the tiling so that their coordinates refer to the full chessboard.</p>
  
  <p>You are given a file, tromino.rkt, which is as follows </p>
  
  <pre><code>#lang racket
  
  (require racket/draw)
  
  (define thickness 6)
  (define offset (floor (/ thickness 2)))
  (define one 100)
  (define two (* 2 one))
  (define a 0)
  (define b one)
  (define c (- two thickness))
  
  (define (mirror coordinates)
    (map (lambda (z) (- one z thickness)) coordinates))
  
  (define x-00 (list c c a a b b))
  (define y-00 (list a c c b b a))
  (define x-01 (mirror x-00))
  (define y-01 y-00)
  (define x-10 x-00)
  (define y-10 (mirror y-00))
  (define x-11 x-01)
  (define y-11 y-10)
  
  (define (make-tromino-path x y)
    (let ((p (new dc-path%)))
      (send p move-to (first x) (first y))
      (send p line-to (second x) (second y))
      (send p line-to (third x) (third y))
      (send p line-to (fourth x) (fourth y))
      (send p line-to (fifth x) (fifth y))
      (send p line-to (sixth x) (sixth y))
      (send p close)
        p))
  
  (define tromino-path-00 (make-tromino-path x-00 y-00))
  (define tromino-path-01 (make-tromino-path x-01 y-01))
  (define tromino-path-10 (make-tromino-path x-10 y-10))
  (define tromino-path-11 (make-tromino-path x-11 y-11))
  
  (define (tromino-path missing-row missing-column)
    (cond ((and (= missing-row 0) (= missing-column 0)) tromino-path-00)
          ((and (= missing-row 0) (= missing-column 1)) tromino-path-01)
          ((and (= missing-row 1) (= missing-column 0)) tromino-path-10)
          ((and (= missing-row 1) (= missing-column 1)) tromino-path-11)
          (else (error 'tromino-path "Called with arguments ~a, ~a (must each be either 0 or 1)"
                   missing-row missing-column))))
  
  (define (draw-board n dc)
    (cond ((= n 1)
           (begin
             (send dc set-smoothing 'unsmoothed)
             (send dc set-pen "white" 0 'solid)
             (send dc set-brush "white" 'solid)
             (send dc draw-rectangle 0 0 two two)
             (send dc set-pen "black" 0 'solid)
             (send dc set-brush "black" 'solid)
             (send dc draw-rectangle 0 0 one one)
             (send dc draw-rectangle one one one one)))
      (else
       (begin
         (draw-board (- n 1) dc)
         (let ((side (* one (expt 2 (- n 1)))))
           (send dc copy 0 0 side side side 0)
           (send dc copy 0 0 (* 2 side) side 0 side))))))
  
  
  (struct tile (row column missing-cell-row missing-cell-column))
  
  (define (show-tile t)
    (printf "(row ~a column ~a missing-cell-row ~a missing-cell-column ~a)\n"
            (tile-row t) (tile-column t)
            (tile-missing-cell-row t) (tile-missing-cell-column t)))
  
  (define (quadrant n row column)
    (let ((half (lambda (n coordinate)
                  (cond ((bitwise-bit-set? coordinate (- n 1)) 1)
                        (else 0)))))
      (list (half n row) (half n column))))
  
  (define (center-tile n row column)
    (let ((q (quadrant n row column))
          (base (- (expt 2 (- n 1)) 1)))
        (tile (+ base (first q)) (+ base (second q)) (first q) (second q))))
  
  (define (missing-cell-within-quadrant n row column quadrant-row quadrant-column)
    (let ((q (quadrant n row column))
          (base (- (expt 2 (- n 1)) 1))
          (sub-coordinate (lambda (coord quad)
                            (cond ((= quad 1) (- coord (expt 2 (- n 1))))
                                  (else coord)))))
      (cond ((and (= (first q) quadrant-row) (= (second q) quadrant-column))
             (list (sub-coordinate row (first q))
                   (sub-coordinate column (second q))))
            (else (list (cond ((= 0 quadrant-row) base)
                              (else 0))
                        (cond ((= 0 quadrant-column) base)
                              (else 0)))))))
  
  (define (upgrade-tiling tiling m quadrant-row quadrant-column)
    (let* ((shift (expt 2 m))
           (row-shift (* quadrant-row shift))
           (column-shift (* quadrant-column shift)))
      (map (lambda (t)
             (tile (+ (tile-row t) row-shift)
                   (+ (tile-column t) column-shift)
                   (tile-missing-cell-row t)
                   (tile-missing-cell-column t)))
           tiling)))
  
  
  (define (make-tiling-png n tiles basename)
    (cond ((or (&lt;= n 0) (empty? tiles))
           (printf "Warning: make-tiling-png called with n too small or an empty tiling. No picture produced\n"))
          (else
           (begin
             (define side (* (expt 2 n) one))
             (define bmap (make-bitmap side side))
             (define dc (new bitmap-dc% (bitmap bmap)))
             (draw-board n dc)
             (send dc set-pen "black" 1 'solid)
             (send dc set-brush "white" 'transparent)
             (send dc draw-rectangle 0 0 side side)
             (send dc set-pen (new pen% (color "red") (width thickness)
                                   (style 'solid) (cap 'projecting) (join 'miter)))
             (send dc set-brush "gray" 'solid)
             (send dc set-smoothing 'unsmoothed)
             (map (lambda (t) (send dc draw-path (tromino-path (tile-missing-cell-row t)
                                                               (tile-missing-cell-column t))
                                    (+ offset (* one (tile-column t)))
                                    (+ offset (* one (tile-row t)))))
                  tiles)
             (send bmap save-file (string-append basename ".png") 'png)))))
  
  (provide tile
           tile-row
           tile-column
           tile-missing-cell-row
           tile-missing-cell-column
           show-tile
           quadrant
           center-tile
           missing-cell-within-quadrant
           upgrade-tiling
           make-tiling-png)
  </code></pre>
  
  <p>You are also given a file, template.rkt, which is as follows:</p>
  
  <pre><code>#lang racket
  
  (require "./tromino.rkt")
  
  (define test-tiling (list (tile 2 5 0 1)))
  (make-tiling-png 3 test-tiling "test-tiling")
  
  **; Your code replaces the null in the following definition**
  (define (tile-board n row column)
    null) 
  
  (define (make-and-show-tiling n row column)
    (make-tiling-png n
                     (tile-board n row column)
                     (format "tiling-~a-~a-~a" n row column)))
  
  ; Initially, these calls will produce no picture
  ; because tile-board returns an empty tiling
  (make-and-show-tiling 1 1 1)
  (make-and-show-tiling 2 0 0)
  (make-and-show-tiling 3 5 2)
  (make-and-show-tiling 3 6 2)
  (make-and-show-tiling 4 5 10)
  (make-and-show-tiling 5 24 21)      
  </code></pre>
  
  <p>I have a very good idea of the concept behind how this works, whereby you split the 2<sup>n</sup> × 2<sup>n</sup> chessboard into 4 separate quadrants, and then place a tromino at the center of the chessboard such that every quadrant now has either one missing cell or one cell that is covered by part of the tromino. Then, call the recursive function to tile each quadrant. The end goal is to have the code run such that each call of (make-and-show-tiling) function at the end of my template.rkt file will produce a picture of the chessboard produced. </p>
  
  <p>I think I am just getting super confused because I have only learnt Java and Python before this, and the format/syntax of DrRacket is so far removed from those languages. I am completely stuck so any help other than actually writing the code for me would be incredibly welcome and gratefully accepted.</p>
  
  <p>Thank you in advance!!</p>