; equalsimp not used in the queens solution
(define (equalsimp l1 l2)
    (cond
      ((null? l1) (null? l2))
      ((null? l2) #f)
      ((eqv? (car l1) (car l2))
       (equalsimp (cdr l1) (cdr l2)))
      (else #f)
      ))

; a board is specified by its size (e.g. 4) and
;   (row col) pairs locating each queen
(define board '(4 (0 1) (1 3) (2 0) (3 2)))

(define (print-horiz-border n)
    (display "-")
    (if (> n 1)
      (print-horiz-border (- n 1))
      ))

(define (print-board board)
    (display "*")
    (print-horiz-border (car board))
    (display "*")
    (newline)
    (print-rows 0 (car board) (cdr board))
    (display "*")
    (print-horiz-border (car board))
    (display "*")
    (newline)
    ) 

(define (print-rows r n queens)
    (display "|")
    (print-row r 0 n queens)
    (display "|")
    (newline)
    (if (< r (- n 1))
        (print-rows (+ r 1) n queens)
        ))

(define (print-row r c n queens)
    (print-square r c queens)
    (if (< c (- n 1))
        (print-row r (+ c 1) n queens)
        ))

(define (print-square r c queens)
    (cond
      ((null? queens) (display "."))
      ((equal? (list r c) (car queens)) (display "Q"))
      (else (print-square r c (cdr queens)))
        ))

(print-board board)





; does (i j) threaten (a b) ?
(define (threat? i j a b)
    (or (= i a)
        (= j b)
        (= (- i j) (- a b))
        (= (+ i j) (+ a b))
        ))

(define (conflict? n m queens)
    (cond
      ((null? queens) #f)
      ((threat? n m (caar queens) (cadar queens)) #t)
      (else (conflict? n m (cdr queens)))
      ))

(define (queen size queens n m)
    (if (< m size)
        (if (not (conflict? n m queens))
            (if (= (+ 1 n) size)
                (print-board (cons size (cons (list n m) queens)))
                (queen size (cons (list n m) queens) (+ 1 n) 0)
                )))
    (if (< m size)
        (queen size queens n (+ 1 m))
        ))

(define (n-queens n)
  (queen n '() 0 0))