# eight queens problem

I want help with writing the operators and states including its precondition and action for the eight queens problem where the queens must not be in conflict. That is placing 8 pieces (the queens) on an 8 by 8 chess board. The pieces must be placed so that no 2 are in the same row, column or diagonal. This should be in LISP.

Attached is an example file of how it is supposed to be represented.

#### Solution Preview

Before all, I would like to invite you to read the following 3 items

# There are 12 solutions.

# In each solution, there are four queens on dark squares and four queens on light squares.

# Just two of the twelve solutions have a queen in a corner

you can also find a full code of this problem below.

To run, simply load file and type (queen n) where

;;;n is the width of board.

;discovers if a piece threatens another

(defun threat (i j a b)

(or (= i a)

(= j b)

(= (- i j) (- a b))

(= (+ i j) (+ a b))))

;discovers if a placement is OK

(defun conflict (n m board)

(cond ((endp board) nil)

((threat n

m

(first (first board))

(second (first board)))

t)

(t (conflict n m (rest board)))))

;;this now prints a board no matter what order it is presented in

(defun print-board (board)

; (sort board #'<= :key #'car)

(format t "~%*")

(print-horizontal-border board)

(format t "*")

(dotimes (row (length board))

(format t "~%|")

(dotimes (column (length board))

(if (= column (second (assoc row board)))

(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 "-")))

;;;The following is Winston/Horn's original queen-finding algorithm.

;;;It does not discriminate sets of solutions that are closed under rotation

;;;and reflection. Thus, a single solution can be equivalent to up to 8 other

;;;solutions.

(defun queen* (size &optional (board nil) (n 0) (m 0))

(unless (= m size)

;;Check for conflict in current row and column

(unless (conflict n m board)

(if (= (+ 1 n) size)

;;If all queens placed, prin solution:

(print-board (reverse (cons (list n m) board)))

;;Otherwise, proceed to next row:

(queen* size (cons (list n m) board) (+ 1 n) 0)))

;;In any case, try with another column

(queen* size board n (+ 1 m))))

;;; This version improves on Winston/Horn in that it displays only one instance

;;;of a closed set of solutions. Thus, 8-queens solution is reduced from 96 to 12.

;;;It achieves this by using a bindings list of already-found solutions. Since a change

;;;made at a deeper level of recursive search must be accessible to a higher level,

;;;the bindings list was made a global parameter that ...

#### Solution Summary

This solution examines an eight queens problem.