1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
;
; Place n queens on a board
; See Winston and Horn Ch. 11
;
; Usage:
; (queens <n>)
; where <n> is an integer -- the size of the board - try (queens 4)
; Do two queens threaten each other ?
(defun threat (i j a b)
(or (eql i a) ;Same row
(eql j b) ;Same column
(eql (- i j) (- a b)) ;One diag.
(eql (+ i j) (+ a b)))) ;the other diagonal
; Is position (n,m) on the board not safe for a queen ?
(defun conflict (n m board)
(cond ((null board) nil)
((threat n m (caar board) (cadar board)) t)
(t (conflict n m (cdr board)))))
; Place queens on a board of size SIZE
(defun queens (size)
(prog (board n m)
(setq board nil)
(setq n 1) ;Try the first row
loop-n
(setq m 1) ;Column 1
loop-m
(cond ((conflict n m board) (go un-do-m))) ;Check for conflict
(setq board (cons (list n m) board)) ; Add queen to board
(cond ((> (setq n (1+ n)) size) ; Placed N queens ?
(print (reverse board)))) ; Print config
(go loop-n) ; Next row which column?
un-do-n
(cond ((null board) (return 'Done)) ; Tried all possibilities
(t (setq m (cadar board)) ; No, Undo last queen placed
(setq n (caar board))
(setq board (cdr board))))
un-do-m
(cond ((> (setq m (1+ m)) size) ; Go try next column
(go un-do-n))
(t (go loop-m)))))
|
