;draws the board.

(define (empty-board r c)
    (if (= r 0) '()
        (se (empty-row r c) (empty-board (- r 1) c) )))

(define (empty-row r c)
    (if (= c 0) '()
        (se (word r c) (empty-row r (- c 1)))))

;lists the places those could not be treated by the knight at 'q'  
;position. It also excluded the 'q' position.

(define (uncovered q e-list)
    (if (empty? e-list) '()
        (let ((rk (first q)) (ck (last q))
              (re (first (first e-list))) 
              (ce (last (first e-list))))
            (if (or (and (= (abs (- rk re)) 2) (= (abs (- ck ce)) 1))
                    (and (= (abs (- ck ce)) 2) (= (abs (- rk re)) 1))
                    (and (= rk re) (= ck ce)))
                (uncovered q (bf e-list))
                (se (first e-list) (uncovered q (bf e-list))))
)))

;back-tracking is in put-a-knight function. The structure is almost the same
;with 8-queen's except the send list part. i need two lists since knight
;problem differs in aim. THANK YOU FOR POSTING IT..


(define (put-a-knight n possible-moves board-empty)
    (if (empty? possible-moves) 
            'this-is-impossible

            (let ((for-first-possible 
                  (knight (- n 1) (uncovered (first possible-moves) board-empty)
                                   (bf possible-moves))))

                (if (equal? for-first-possible 'this-is-impossible)
                    (put-a-knight n (bf possible-moves) board-empty)
                    (se (first possible-moves) for-first-possible))
            )
))

;knight checks for the stopping condition for recursive calls,
;it is mutually recursive with put-a-knight.


(define (knight n board-empty possible-moves) 
    (cond 
        ((and (empty? board-empty) (= n 0)) '())
        (else (put-a-knight n possible-moves board-empty))
))

;i write double-list to avoid calling recursive board-empty functions 2 times 

(define (double-list n list)
    (knight n list list))

;cover is main function. it also converts the result to the correct form
;with letters. 

(define (cover n k)
    (let ((places  (double-list k (empty-board n n))) (letters '(a b c d e f g h                                                                        i j)))
   (if (equal? places 'this-is-impossible) places  
    (every (lambda (x) (word (item (first x) letters) (last x))) places))))