My assignment is to write 2 lisp functions to solve the n-queens for
an n by n board. One that will take in a (n), the board size as
parameter. It will return all configuartions of the n by n board i.e
(1 2 3 4 5) for board size 5. The second function is supposed to
eliminate all invalid or illegal boards. Namely, queens in the same
column, row or diagonal.
Format: You can represent a board configuration with a simple n
element list(c1 c2 c3 c4 ... cn), ci corresponds to the column
position of i-th queen inthe i-th row. For example, (1 3 2 4) would
correspond to the 4 queens
in positions (1,1) (row 1, column 1), (2,3) (row 2, column 3), (3,2)
(row 3, column 2), and (4,4) (row 4, column 4). Note that in our
representation we do not use double indexes: the i-th queen is placed
in the i-th row and its column index is ci.
Posted Via Usenet.com Premium Usenet Newsgroup Services
----------------------------------------------------------
** SPEED ** RETENTION ** COMPLETION ** ANONYMITY **
----------------------------------------------------------
http://www.usenet.com
·······@yahoo-dot-com.no-spam.invalid (aref) wrote:
> i.e (1 2 3 4 5) for board size 5
if you really mean, that (1 2 3 4 5) is a valid result for size 5, then
this is your function:
(defun a (n)
(loop for i from 1 to n collect i))
> The second function is supposed to
> eliminate all invalid or illegal boards. Namely, queens in the same
> column, row or diagonal.
(defun b (board)
board)
but you should think again about your specification. For #'a something
like this would be more useful:
(a 3) -> ((3 3 3) (3 3 2) (3 3 1) (3 2 3) (3 2 2) (3 2 1) (3 1 3) (3 1 2)
(3 1 1) (2 3 3) (2 3 2) (2 3 1) (2 2 3) (2 2 2) (2 2 1) (2 1 3) (2 1 2)
(2 1 1) (1 3 3) (1 3 2) (1 3 1) (1 2 3) (1 2 2) (1 2 1) (1 1 3) (1 1 2)
(1 1 1))
and a possible definition for #'a:
(defun a (n)
(let ((result))
(funcall
(funcall
#'(lambda (m)
((lambda (u)
(funcall m #'(lambda (&rest arg)
(apply (funcall u u) arg))))
#'(lambda (u)
(funcall m #'(lambda (&rest arg)
(apply (funcall u u) arg))))))
#'(lambda (fun)
#'(lambda (n i l)
(loop for j from 1 to n do
(let ((c (append l (list j))))
(if (< i n)
(funcall fun n (1+ i) c)
(push c result)))))))
n
1
nil)
result))
and then #'b looks a bit more complicated:
(defun b (boards)
(flet ((valid (board)
(loop for (i . rest) on board
finally (return board) do
(loop for j in rest
with ofs = 0
always (incf ofs) do
(when (or (eql j i)
(eql j (+ i ofs))
(eql j (- i ofs)))
(return-from valid nil))))))
(loop for board in boards when (valid board) collect it)))
This finds all valid boards:
(b (a 5)) ->
((5 3 1 4 2) (5 2 4 1 3) (4 2 5 3 1) (4 1 3 5 2) (3 5 2 4 1) (3 1 4 2 5)
(2 5 3 1 4) (2 4 1 3 5) (1 4 2 5 3) (1 3 5 2 4))
With this function you can generate the sequence in OEIS:
http://www.research.att.com/projects/OEIS?Anum=A000170
(loop for i from 1 to 7 collect (length (b (a i)))) ->
(1 0 0 2 10 4 40)
(but over 7 it starts swapping on my computer, because the algorithm is
not good enough)
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
It is considered good form to give the group a precis of your attempts
to date on the project rather than just ask someone else to write it
from scratch for you.
Tim
aref wrote:
> My assignment is to write 2 lisp functions to solve the n-queens for
> an n by n board. One that will take in a (n), the board size as
> parameter. It will return all configuartions of the n by n board i.e
> (1 2 3 4 5) for board size 5. The second function is supposed to
> eliminate all invalid or illegal boards. Namely, queens in the same
> column, row or diagonal.
>
> Format: You can represent a board configuration with a simple n
> element list(c1 c2 c3 c4 ... cn), ci corresponds to the column
> position of i-th queen inthe i-th row. For example, (1 3 2 4) would
> correspond to the 4 queens
> in positions (1,1) (row 1, column 1), (2,3) (row 2, column 3), (3,2)
> (row 3, column 2), and (4,4) (row 4, column 4). Note that in our
> representation we do not use double indexes: the i-th queen is placed
> in the i-th row and its column index is ci.