8 Queens Problem

The eight queens problem is a real life problem for chess players. The task is to place eight queens on a chessboard so that none attacks any other. A solution is shown below:

(1 5 8 6 3 7 2 4)

Q
				Q
							Q
					Q
		Q
						Q
	Q
			Q

So how would you explain, to a child, how to reach such a solution? One possibility might be this narrative: Place the first queen in square 1 of row 1. Place the next in the next row at column 1 and look for attacks. If there are any,and there are now columns left, move this queen to the next column. If there are no columns left, go back to the previous queen, move it  over 1 column and then come back the the . When all 8 queens are on the board you're done.

To explain to a computer we will talk on the same level but with carefully controlled expressions. The language we will use her will be the language of rules. Since there is no chessboard in the computer we need to capture the state of th it at each point some other way. We choose the keep facts like this:  (queens 1 5 8 6 3 7 2 4). It is to be interpreted as giving the row and column for each of the queens 1..8. The column for the 4th queen  is the 4th value in the list, etc. We know how many queens we need but we start with none.  So start with two pieces of information:

(deffacts setup

   (nQueens 8)   ; can change number for any size

   (queens)

)

With an ordered list queens, they can never be in the same row. We easily check columns j if some column number appears twice.

(defrule checkCol

   (declare (salience 100))    ;must be check before deciding!

   (queens $? ?c $? ?c)

   =>

   (assert (ATTACK)))

On the board above, we can see that the queens do not attack on diagonals either. With the list, we will have to calculate whether (1,1),(2,1), (3,3)  etc. share rank, file or diagonal. The row is the list location. The column is the entry.  We use the length$ CLIPS function to determine the number of items in a list. It we look at the whole list we know where the last one is. If we find something in the list its position is the number before +1. In out rule we will let the queen fact be matched twice.

What about the calculation? In the diagram below, Queen 1 attacks queen 3 because we can get to Q3 by moving down 2 and right 2 from Q1. Vice versa, we can move up 2 rows and left two columns to go from Q3 to Q1. On any diagonal, the up/down and left/right counts will be the same. For Q1 and Q3, this is true,  For Q2 and Q3 this is not true.

Q1	Q2
		Q3

Whenever we want to know if one queen attacks another we only need find their rows and columns and ask whether the absolute values of the respective differences are equal. We let the queen fact be matched twice to simplify arithmetic.

(defrule checkDiag

   (declare (salience 100))    ;must be check before deciding!

   (queens $?Qs)

   (queens $?A ?c2 $? ?c1)

   (test (= (abs (- (+ (length$ $?A) 1) (length$ $?Qs)))

            (abs (- ?c1 ?c2))))

=>

   (assert (ATTACK)))

Now let us return to our overall process as described above. To make it a little more definite we may construct a decision matrix. The method is creating a table for what situations call for what actions. That requires we know how to recognize the various situations. From the above some are: 1) Do we have all queens yet? 2) Is the current list of queen locations OK? 3) Is there more column in this row? Let’s see if these are enough.

We construct a decision matrix relating situations defined by our questions to actions we may need to take. Given three question, each true or false, there will be 8 possible arrangements of questions. The actions we have mentioned above are four: 1) The puzzle is solved 2) (all is OK) we can add a new queen 3) We try the next column 4) we re-try the previous queen in a new column (and start over with the last queen).  This full beginning decision table is shown below.

All queens known?	ANy Attacks?	Next column?	ACTION/state
Y	N	Y	solved
Y	N	N	solved
Y	Y	Y	Try next column
Y	Y	N	Retry previous with new column
N	N	Y	Add a queen
N	N	N	Add a queen
N	Y	Y	Try next column
N	Y	N	Retry previous with new column

We can reduce the table using logic. We can eliminate don’t cares. We can move the situation rows that have the same action together. We can consolidate rows were a question being true of false make no difference in action. We then get the the following:

All queens known?	Any attacks?	Next column?	ACTION
Y	N		solved
N	N		Add a queen
	Y	Y	Try next column
	Y	N	Retry previous with new column

It is not necessary to reduce the decision matrix. However, doing so can reduce the number of situations we must recognize.

How do we answer the questions about a situation in our program? Recall that the situation will be something like (queens 1 5 8 6 3 7 2 4) or like (queens 1 5 8 6 2).  So a list is complete when its length is the number of queens we need.

Since we have an attack function, we can use it to assert a fact whenever the queen's’ list has one. We assume we have used our attack function to check for any  attack. So we can recognize a solution with the following rule:

(defrule Solved

   (nQueens ?nq)

   (queens $?Qs)

   (test (= (length$ $?Qs) ?nq))

   (not (ATTACK))

=>

   (halt)

   (printout t $?Qs crlf))

When to add a queen? When there are no attacks  but we do not have all the queens.

(defrule addQueen

   (nQueens ?nq)

?f<-(queens $?Qs)

   (test (< (length$ $?Qs) ?nq))

   (not (ATTACK))

=>

   (retract ?f)

   (assert (queens $?Qs 1)))

Notice that we capture the old index during the match. That index is used to delete the old queens fact. The new queens fact has one more queen, initially in column 1.

Our third situation was when the current queens have an attack but there is a next row. We ‘move’ the queen over a column. (We also remove the attack fact since we have a new queens):

‘(defrule nextColumn

   (nQueens ?nq)

?f<-(queens $?Qs ?col)

   (test (<= ?col ?nq))

?g<-(ATTACK)

=>

   (retract ?f ?g)

   (assert (queens $?Qs (+ ?col 1))))

Finally, if there is no next column, we have exhausted trys at this point and must backtrack. That is we give up the current queen and return to the previous to try a new value there. For us that just means drop the last and increment that before the last by 1:

(defrule backtrack   ; exhausted all possibilities!

   (nQueens ?nq)

?f<-(queens $?Qs ?qBefore ?q)

   (test (> ?q ?nq))    

?g<-(ATTACK)

=>

   (retract ?f ?g)

   (assert (queens $?Qs (+ ?qBefore 1))))

Although we planned our logic carefully, note the importance of or list of queens. It records the queens in order, but we also use it to go back to the previous queen. Any list can record things in order but when we always add and extract from the same end, we get a stack.  We are using as a stack. Like a pile of plates, the first plate down is the last plate out and vice versa. Many approaches use this to control their operation. Here we used it to set each new queen in terms of the old and to return from the current failed queen to the previous.

If you think about the history of the process, we are searching a tree of possibilities. The tree of queen positions is shown below. A Stack is a convenient way of organizing how deep we are in the tree and remembering how to retreat to the previous level - all the way to the origin if we must.

And what are we doing with the stack? We are exploring the state space. The state space is all the possible choices that could be made. The stack holds the set of choices currently being considered. The space gets large very quickly. Basically is nn if all choices are acceptable everywhere and n! if the choices must exhaust the possibilities. We show the tree for 4 queens below, with arrows to connect the tested choices. Successful choices have bold arrows.

INSERT FINISHED GRAPHS HERE

NOTES

The code finds the solution for eight queens in a second  on a PC. It can use any strategy because we accounted for all logical possibilities in our rules.

Complete code:

The code below contains other options for checking attacks. The function and rule using it have been commented out.

; Queens by Backtracking

(deffacts setup

   (nQueens 8)

   (queens)

)

; === moves

; ----- if OK

(defrule addQueen

   ;(declare (salience -10))

   (nQueens ?nq)

?f<-(queens $?Qs)

   (not (ATTACK))

   (test (< (length$ $?Qs) ?nq))

=>

   (retract ?f)

   (assert (queens $?Qs 1)))

(defrule Solved

   (nQueens ?nq)

   (queens $?Qs)

   (not (ATTACK))

   (test (= (length$ $?Qs) ?nq))

=>

   (halt)

   (printout t $?Qs crlf))

; ----- if ATTACKed

(defrule nextColumn

   (nQueens ?nq)

?f<-(queens $?Qs ?col)

   (test (<= ?col ?nq))

?g<-(ATTACK)

=>

   (retract ?f ?g)

   (assert (queens $?Qs (+ ?col 1))))

(defrule backtrack   ; exhausted all possibilities!

   ;(declare (salience 30))

   (nQueens ?nq)

?f<-(queens $?Qs ?qBefore ?q)

   (test (> ?q ?nq))    ; changed

?g<-(ATTACK)

=>

   (retract ?f ?g)

   (assert (queens $?Qs (+ ?qBefore 1))))

; ==== ATTACKures

(defrule exhausted

   (declare (salience 30))

   (nQueens ?nq)

   (queens $? ?q)

   (test (> ?q ?nq))     ; changed

=>

   (assert (ATTACK)))

   

; Deleted the next two constructs in favor of avoiding functions and simpler rules

;(deffunction queenAttack (?r1 ?c1 ?r2 ?c2)

;   (if (or (= ?c1 ?c2)

;           (= ?r1 ?r2))

;    then TRUE

;    else (= (abs (- ?r1 ?r2))(abs (- ?c1 ?c2)))))

;

;(defrule attacks

;    (declare (salience 10))

;    (queens $?A ?c1 $?B ?c)

;    (not (ATTACK))

;    (test (queenAttack (+ (length$ $?A) 1)

;                       ?c1

;                       (+ (length$ $?A) 1 (length$ $?B) 1) ; changed

;                       ?c))

;=>

;    (assert (ATTACK)))

;

; the rules below may fire multiple times but once is just enough

; If you condition these rules with (not (ATTACK))  you avoid the extra firings

(defrule checkCol

   (declare (salience 100))

   (queens $? ?c $? ?c)

   =>

   (assert (ATTACK)))

(defrule checkDiag

   (declare (salience 100))

   (queens $?Qs)

   (queens $?A ?c2 $? ?c1)

   (test (= (abs (- (+ (length$ $?A) 1) (length$ $?Qs)))

            (abs (- ?c1 ?c2))))

=>

   (assert (ATTACK)))