"Rob" <··············@hotmail.com> wrote in message
·································@posting.google.com...
> Hi i'm at uni and have a Lisp assignment where I have to produce a
> variation of the 8 queens problem. I've decided to add a third
> dimention to the problem but i'm running into difficulties and out of
> time (of course, i'm a student so it all gets left to the last
> minute).
>
> We were given some code to calculate the problem in 2D, it is slightly
> incomplete as it simply fills the board up with queens so as they
> can't take each other, it does not stop at 8. This is the code,
>
> (DEFUN THREAT (I J A B)
> (OR (= I A)
> (= J B)
> (= (- I J) (- A B))
> (= (+ I J) (+ A B))))
>
> (DEFUN CONFLICT (N M BOARD)
> (COND ((NULL BOARD) NIL)
> ((OR (THREAT N M (FIRST (FIRST BOARD)) (CAR (REST (FIRST BOARD))))
> (CONFLICT N M (REST BOARD))))))
>
> (DEFUN QUEEN (SIZE) (QUEEN-AUX NIL 0 SIZE))
>
> (DEFUN QUEEN-AUX (BOARD N SIZE)
> (COND ((= N SIZE) (BOARD-PRINT BOARD))
> (T (QUEEN-SUB BOARD N 0 SIZE))))
>
> (DEFUN QUEEN-SUB (BOARD N M SIZE)
> (COND ((= M SIZE))
> (T (COND ((CONFLICT N M BOARD))
> (T (QUEEN-AUX (CONS (LIST N M) BOARD) (+ N 1) SIZE)))
> (QUEEN-SUB BOARD N (+ M 1) SIZE))))
>
> (DEFUN BOARD-PRINT (BOARD) (BOARD-PRINT-AUX BOARD (LENGTH BOARD)))
>
> (DEFUN BOARD-PRINT-AUX (BOARD SIZE)
> (TERPRI)
> (COND ((NULL BOARD))
> (T (BOARD-PRINT-SUB (FIRST (REST (FIRST BOARD))) 0 SIZE)
> (BOARD-PRINT-AUX (REST BOARD) SIZE))))
>
> (DEFUN BOARD-PRINT-SUB (COLUMN N SIZE)
> (COND ((= N SIZE) )
> (T (COND ((= COLUMN N) (PRINC "Q"))
> (T (PRINC "-")))
> (PRINC " ")
> (BOARD-PRINT-SUB COLUMN (+ N 1) SIZE))))
>
> It works fine now i've been trying to ammend this code so it will work
> in three dimentions. I've managed to get the THREAT and CONFLICT
> funtions working correctly, well at least I think so. I've written
> the rest of the code, except for printing the board. So far I've just
> been trying to get it so run as the original, later I will ammened it
> to calculate for only 8 queens. This is what I've done so far
>
> ; is there a threat
> (DEFUN THREAT (C B A Z Y X)
> (OR (= (sqrt (* (- A X) (- A X))) ; Here we check for 3D Diagonals
> (sqrt (* (- B Y) (- B Y))) ; We need to get the Absolute value of
> (sqrt (* (- C Z) (- C Z)))) ; the difference, hence the squaring &
> rooting
check out ABS as in (abs (- b y)). Squaring and square-rooting stikes me as
a very computationally expensive approach, especially if you are searching a
3d chess board!
> (AND (= A X) (= C Z))
> (AND (= B Y) (= C Z))
> (AND (= A X) (= B Y))
> (AND (= (- A B) (- X Y)) (= C Z))
> (AND (= (+ A B) (+ X Y)) (= C Z))))
>
> ;Is there a confict??
> (DEFUN CONFLICT (Z Y X BOARD)
> ;End if the board is empty
> (COND ((NULL BOARD) NIL)
> ;Test if sent position threatens any queens currenty on the board
> ((OR (THREAT Z Y X (FIRST (FIRST BOARD)) (NTH 1 (FIRST BOARD)) (NTH 2
> (FIRST BOARD)))
> (CONFLICT Z Y X (REST BOARD))))))
>
> ;To get all solutions this function gets a solution for each posible
> ;starting postion for a queen
> (DEFUN QUEEN3D (SIZE) (QUEEN3D-Z NIL 0 SIZE))
>
> ;Start with the Z Plane
> (DEFUN QUEEN3D-Z (BOARD Z SIZE)
> ;Finish calculation if done all squaress
> (COND ((= Z SIZE) (PRINT-BOARDS BOARD))
> ;Carry on Searching if not
> (T (QUEEN3D-Y BOARD Z 0 SIZE))))
>
> ;Do The Y Plane
> (DEFUN QUEEN3D-Y (BOARD Z Y SIZE)
> ;Do next Z plane if Y complete
> (COND ((= Y SIZE) (QUEEN3D-Z BOARD (+ Z 1) SIZE))
> ;Carry on searching if not
> (T (QUEEN3D-X BOARD Z Y 0 SIZE))))
>
> (DEFUN QUEEN3D-X (BOARD Z Y X SIZE)
> ;Finish if row complete or 8 queens
> (COND ((= X SIZE))
> ;Test if this square can be used
> (T (COND ((CONFLICT Z Y X BOARD))
> ; Square OK so add it to the list
> (T (QUEEN3D-Y (CONS (LIST Z X Y) BOARD) Z (+ Y 1) SIZE)))
> ;square can't be used so try next
> (QUEEN3D-X BOARD Z Y (+ X 1) SIZE))))
>
> ;Print the Board
> (DEFUN PRINT-BOARDS (BOARDS) (VALUES BOARDS))
>
> When I run the (QUEEN3D SIZE) function it only returns T and won't
> print the board. I've tried running the (QUEEN3D-Z) funtions with
> some data so that it will simply complete and it will print out the
> board. So I suspect the problem lies in the (QUEEN3D-Y) or
> (QUEEN3D-X) functions, but I may be wrong. I expect I've just done
> something really stupid somewhere like but I've checked and reacheck
> the code so many times that I'm adamant it should work.
I looked through your code a bit...I see no print or princ or format calls.
Your print-boards function doesn't. In fact it does nothing but return its
argument...?
If that is not the real code but a cut n' paste error, the next thing I
would investigate is why the first branch of QUEEN3D-Z is never taken (not
saying it isn't, just that is where to look if you still get no printing)
--
Coby Beck
(remove #\Space "coby 101 @ bigpond . com")
Thanks coby,
Sorry, the print boards function was supposed to say (print board), so
it simply prints the list for now, eventualy I'll get it to draw the
boards.
The first branch of the (queen3d-z) function does run, if I run the
function like so
(queen3d-z '((0 0 0) (1 3 4)) 4 4)
It will print the list, however if it needs to call the (queen3d-y)
function it will just return true. I think the problem lies in my
logic :-(. I'm used to programming in C++, Java, etc. And am having
trouble getting my head round all this recursion stuff.
What I think should be happening is (Queen3d-z) will recursivly call
(queen3d-y) which will recusivly call (queen3d-x). When a solution is
found, ie the whole board is searched it will print it. And hopefuly
lisp should keep going until it's found all posible solutions, I hope.
I know the code works to a certain extent as with a little
modification I can get it to print out one single solution and then
stop, but this is no good cos it has to find them all.
OK, I've just worked it out, I can't believe it, I forgot to call
(QUEEN3D-Y) from (QUEEN3D-X) if it's finished searching that row;
(DEFUN QUEEN3D-X (BOARD Z Y X SIZE)
;Finish if row complete or 8 queens
(COND ((= X SIZE) (queen3d-y board Z (+ y 1) size)) ; <---HERE
;Test if this square can be used
(T (COND ((CONFLICT Z Y X BOARD))
; Square OK so add it to the list
(T (QUEEN3D-Y (CONS (LIST Z X Y) BOARD) Z (+ Y 1) SIZE)))
;square can't be used so try next
(QUEEN3D-X BOARD Z Y (+ X 1) SIZE))))
Ok Thank for the help, I'll post the working prog here, incase
anyone's interested, I' shocked at how many solutions there are for a
4x4x4 board, I've assumed that on a 3D board a queen can move
horizontaly on the Z axis and diagonaly in 3D by moving on a line that
increases/decreases by 1 square on each axis. Any how here's the code
and thanks again;
; is there a threat
(DEFUN THREAT (C B A Z Y X)
(OR (= (ABS (- A X)) ; Here we check for 3D Diagonals
(ABS (- B Y)) ; We need to get the Absolute value of
(ABS (- C Z))) ; the difference
(AND (= A X) (= C Z))
(AND (= B Y) (= C Z))
(AND (= A X) (= B Y))
(AND (= (- A B) (- X Y)) (= C Z))
(AND (= (+ A B) (+ X Y)) (= C Z))))
;Is there a confict??
(DEFUN CONFLICT (Z Y X BOARD)
;End if the board is empty
(COND ((NULL BOARD) NIL)
;Test if sent position threatens any queens currenty on the board
((OR (THREAT Z Y X (FIRST (FIRST BOARD)) (NTH 1 (FIRST BOARD)) (NTH 2
(FIRST BOARD)))
(CONFLICT Z Y X (REST BOARD))))))
;To get all solutions this function gets a solution for each posible
;starting postion for a queen
(DEFUN QUEEN3D (SIZE) (QUEEN3D-Z NIL 0 SIZE))
;Start with the Z Plane
(DEFUN QUEEN3D-Z (BOARD Z SIZE)
;Finish calculation if done all squaress
(COND ((OR (= Z SIZE) (= (LENGTH BOARD) 8)) (COND ((= (LENGTH BOARD)
8) (PRINT-BOARDS BOARD))))
;Carry on Searching if not
(T (QUEEN3D-Y BOARD Z 0 SIZE))))
;Do The Y Plane
(DEFUN QUEEN3D-Y (BOARD Z Y SIZE)
;Do next Z plane if Y complete
(COND ((OR (= Y SIZE) (= (LENGTH BOARD) 8)) (QUEEN3D-Z BOARD (+ Z 1)
SIZE))
;Carry on searching if not
(T (QUEEN3D-X BOARD Z Y 0 SIZE))))
;Do The X plane
(DEFUN QUEEN3D-X (BOARD Z Y X SIZE)
;Finish if row complete or 8 queens
(COND ((OR (= X SIZE) (= (LENGTH BOARD) 8)) (queen3d-y board Z (+ y
1) size))
;Test if this square can be used
(T (COND ((CONFLICT Z Y X BOARD))
; Square OK so add it to the list
(T (QUEEN3D-Y (CONS (LIST Z X Y) BOARD) Z (+ Y 1) SIZE)))
;square can't be used so try next
(QUEEN3D-X BOARD Z Y (+ X 1) SIZE))))
;Print the Board
(DEFUN PRINT-BOARDS (BOARDS) (PRINT BOARDS))