Explore BrainMass
Share

# Operators for eight queens puzzle

Computer Science, Artificial Intelligence
Year 2
operator/sate world to implememnt the eight queens problem
--------------------------------------------------------------------------------
I want help with writing the opeartors which contains the states includiing its precondition and action for the eight queens problem. that is placing 8 pieces (the queens) on an 8 by 8 chess board. i want the code to be as basic and uncomplicated as possible.

attched is an example file(wwtt) of how the operators should look like.the states preferably should be in a list format when tested( strucutre will do also). i've also included the search code i'll be using to implement the searches after the operators are provided. so if possible run a breadth and random search to see if your states apply to the provided code and an example of how it was run provided as well.thanx
NB: i'm not worRied about if a queen attacks another queen at the moment. just simple operators to simulate the problem in an operator/state world will do. it will help if you looked at the file attached.

#### Solution Preview

Dear my friend
Thank you very much to choosing our group to helping you. We would be so happy if we could help you to find your solution.

Before all, I would like to invite you to read the following 3 items for a general problem.

# 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.
Reading this will give you a good idea .

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

\$2.19