;;; THE INTRO TO AI SHOW
;;; Summer Session I 1999
;;;
;;; DEMO:
;;; The n-queens problem, for competition
;;; between Selmer and Ralph
;;;
;;; This code is lean on comments -- try to see
;;; how it works.  What happens if you try to
;;; print a board with queens in the same row?
;;; Same column?...
;;;
;;; Selmer Bringsjord


(defun print-board (board)
  (format t "~%*")
  (print-horizontal-border board)
  (format t "*")
  (dolist (queen-coordinates board)
    (format t "~%|")
    (dotimes (column (length board))
      (if (= column (second queen-coordinates))
        (format t " Q")
        (format t " .")))
    (format t " |"))
  (format t "~%*")
  (print-horizontal-border board)
  (format t "*"))

(defun print-horizontal-border (board)
  (dotimes (n (+ 1 (* 2 (length board))))
    (format t "-")))

(defun threatp (i j a b)
  "Checks to see if two queens threaten each other."
  (or (= i a)
      (= j b)
      (= (- i j) (- a b))
      (= (+ i j) (+ a b))))

(defun unsafe (n m board)
  "Checks to see if the position n m for the new queen is safe."
  (cond ((endp board) nil)
        ((threatp n m 
                 (first (first board))
                 (second (first board)))
         t)
        (t (unsafe n m (rest board)))))

(defun queen (size &optional (board nil) (n 0) (m 0))
  (unless (= m size)
    (unless (unsafe n m board)
      (if (= (+ 1 n) size)
        (print-board (reverse (cons (list n m) board)))
        (queen size (cons (list n m) board) (+ 1 n) 0)))
    (queen size board n (+ 1 m))))