Explore BrainMass

eight queens problem

I want help with writing the opeartors and states includiing 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

Thank you very much to choosing our group to help you.

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
(first (first board))
(second (first board)))
(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

(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 ...

Solution Summary

This job examines an eight queens problem.