八皇后问题解法（Common Lisp实现）

如何才能在一张国际象棋的棋盘上摆上八个皇后而不致使她们互相威胁呢？这个著名的问题可以方便地通过一种树搜索方法来解决。

首先，我们需要写一个函数来判断棋盘上的两个皇后是否互相威协。在国际象棋中，皇后可以沿棋盘的行、列和通过它们所在位置的两条对角线移动。如果我们给行和列标上数字，我们就可以对棋盘上的位置编码。

使用函数threat判断两个位置是否互相威胁；函数conflict用来判断向棋盘上添加一个新皇后时，位置(n m)是否是安全的；函数queen列出八皇后问题的解（对于2X2和3X3的棋盘无解）。

Lisp源代码

;判断两个位置(i j)和(a b)是否互相威胁
(defun threat (i j a b)
	(or
		(equal i a) 			;同行，
		(equal j b) 			;同列，
		(equal(- i j)(- a b))	;西南-东北对角线. 
		(equal(+ i j)(+ a b))	;西北-东南对角线
	)
)
;判断向棋盘上添加一个新皇后时，位置(n m)是否是安全的
(defun conflict (n m board)
	(cond 
		((null board) nil) ;棋盘为空时，不冲突
		((or (threat n m (caar board) (cadar board)) 
			 (conflict n m (cdr board))))	;递归调用
	)
)
;列出八皇后问题的解, 棋盘大小为size X size
(defun queen(size)
	(prog (n m board)
		(setq n 1)	;第一行
	loop_n 
		(setq m 1) 	;第一列
	loop_m
		(cond ((conflict n m board) (go un_do_m)))	;检查冲突. 若冲突，则转un_do_m
		(setq board (cons (list n m) board))		;若不冲突，则在棋盘上加一个皇后
		(cond((> (setq n (+ n 1)) size)		;进行下一行
			(print (reverse board))) 				;如n放完，打印结果
		) 
		(go loop_n) 								;去找列
	un_do_n
		(cond
			((null board)(return 'finished))		;所有可能情况找完
			(t
				(setq 		;用移去最后放置的一个皇后来取消最后一个结局
					m (cadar board) 	
					n (caar board) 
					board (cdr board)
				)
			)
		)
	un_do_m 
		(cond
			((> (setq m (+ m 1)) size)
				(go un_do_n)) 	;进行下一列
			(t (go loop_m))
		)
	)
)

程序运行结果

在大小4*4的棋盘上运行命令为：

(queen 4)

运行结果为：

 

在大小8*8的棋盘上运行命令为：

(queen 8)

一共有92个解，列出如下：

((1 1) (2 5) (3 8) (4 6) (5 3) (6 7) (7 2) (8 4))

((1 1) (2 6) (3 8) (4 3) (5 7) (6 4) (7 2) (8 5))

((1 1) (2 7) (3 4) (4 6) (5 8) (6 2) (7 5) (8 3))

((1 1) (2 7) (3 5) (4 8) (5 2) (6 4) (7 6) (8 3))

((1 2) (2 4) (3 6) (4 8) (5 3) (6 1) (7 7) (8 5))

((1 2) (2 5) (3 7) (4 1) (5 3) (6 8) (7 6) (8 4))

((1 2) (2 5) (3 7) (4 4) (5 1) (6 8) (7 6) (8 3))

((1 2) (2 6) (3 1) (4 7) (5 4) (6 8) (7 3) (8 5))

((1 2) (2 6) (3 8) (4 3) (5 1) (6 4) (7 7) (8 5))

((1 2) (2 7) (3 3) (4 6) (5 8) (6 5) (7 1) (8 4))

((1 2) (2 7) (3 5) (4 8) (5 1) (6 4) (7 6) (8 3))

((1 2) (2 8) (3 6) (4 1) (5 3) (6 5) (7 7) (8 4))

((1 3) (2 1) (3 7) (4 5) (5 8) (6 2) (7 4) (8 6))

((1 3) (2 5) (3 2) (4 8) (5 1) (6 7) (7 4) (8 6))

((1 3) (2 5) (3 2) (4 8) (5 6) (6 4) (7 7) (8 1))

((1 3) (2 5) (3 7) (4 1) (5 4) (6 2) (7 8) (8 6))

((1 3) (2 5) (3 8) (4 4) (5 1) (6 7) (7 2) (8 6))

((1 3) (2 6) (3 2) (4 5) (5 8) (6 1) (7 7) (8 4))

((1 3) (2 6) (3 2) (4 7) (5 1) (6 4) (7 8) (8 5))

((1 3) (2 6) (3 2) (4 7) (5 5) (6 1) (7 8) (8 4))

((1 3) (2 6) (3 4) (4 1) (5 8) (6 5) (7 7) (8 2))

((1 3) (2 6) (3 4) (4 2) (5 8) (6 5) (7 7) (8 1))

((1 3) (2 6) (3 8) (4 1) (5 4) (6 7) (7 5) (8 2))

((1 3) (2 6) (3 8) (4 1) (5 5) (6 7) (7 2) (8 4))

((1 3) (2 6) (3 8) (4 2) (5 4) (6 1) (7 7) (8 5))

((1 3) (2 7) (3 2) (4 8) (5 5) (6 1) (7 4) (8 6))

((1 3) (2 7) (3 2) (4 8) (5 6) (6 4) (7 1) (8 5))

((1 3) (2 8) (3 4) (4 7) (5 1) (6 6) (7 2) (8 5))

((1 4) (2 1) (3 5) (4 8) (5 2) (6 7) (7 3) (8 6))

((1 4) (2 1) (3 5) (4 8) (5 6) (6 3) (7 7) (8 2))

((1 4) (2 2) (3 5) (4 8) (5 6) (6 1) (7 3) (8 7))

((1 4) (2 2) (3 7) (4 3) (5 6) (6 8) (7 1) (8 5))

((1 4) (2 2) (3 7) (4 3) (5 6) (6 8) (7 5) (8 1))

((1 4) (2 2) (3 7) (4 5) (5 1) (6 8) (7 6) (8 3))

((1 4) (2 2) (3 8) (4 5) (5 7) (6 1) (7 3) (8 6))

((1 4) (2 2) (3 8) (4 6) (5 1) (6 3) (7 5) (8 7))

((1 4) (2 6) (3 1) (4 5) (5 2) (6 8) (7 3) (8 7))

((1 4) (2 6) (3 8) (4 2) (5 7) (6 1) (7 3) (8 5))

((1 4) (2 6) (3 8) (4 3) (5 1) (6 7) (7 5) (8 2))

((1 4) (2 7) (3 1) (4 8) (5 5) (6 2) (7 6) (8 3))

((1 4) (2 7) (3 3) (4 8) (5 2) (6 5) (7 1) (8 6))

((1 4) (2 7) (3 5) (4 2) (5 6) (6 1) (7 3) (8 8))

((1 4) (2 7) (3 5) (4 3) (5 1) (6 6) (7 8) (8 2))

((1 4) (2 8) (3 1) (4 3) (5 6) (6 2) (7 7) (8 5))

((1 4) (2 8) (3 1) (4 5) (5 7) (6 2) (7 6) (8 3))

((1 4) (2 8) (3 5) (4 3) (5 1) (6 7) (7 2) (8 6))

((1 5) (2 1) (3 4) (4 6) (5 8) (6 2) (7 7) (8 3))

((1 5) (2 1) (3 8) (4 4) (5 2) (6 7) (7 3) (8 6))

((1 5) (2 1) (3 8) (4 6) (5 3) (6 7) (7 2) (8 4))

((1 5) (2 2) (3 4) (4 6) (5 8) (6 3) (7 1) (8 7))

((1 5) (2 2) (3 4) (4 7) (5 3) (6 8) (7 6) (8 1))

((1 5) (2 2) (3 6) (4 1) (5 7) (6 4) (7 8) (8 3))

((1 5) (2 2) (3 8) (4 1) (5 4) (6 7) (7 3) (8 6))

((1 5) (2 3) (3 1) (4 6) (5 8) (6 2) (7 4) (8 7))

((1 5) (2 3) (3 1) (4 7) (5 2) (6 8) (7 6) (8 4))

((1 5) (2 3) (3 8) (4 4) (5 7) (6 1) (7 6) (8 2))

((1 5) (2 7) (3 1) (4 3) (5 8) (6 6) (7 4) (8 2))

((1 5) (2 7) (3 1) (4 4) (5 2) (6 8) (7 6) (8 3))

((1 5) (2 7) (3 2) (4 4) (5 8) (6 1) (7 3) (8 6))

((1 5) (2 7) (3 2) (4 6) (5 3) (6 1) (7 4) (8 8))

((1 5) (2 7) (3 2) (4 6) (5 3) (6 1) (7 8) (8 4))

((1 5) (2 7) (3 4) (4 1) (5 3) (6 8) (7 6) (8 2))

((1 5) (2 8) (3 4) (4 1) (5 3) (6 6) (7 2) (8 7))

((1 5) (2 8) (3 4) (4 1) (5 7) (6 2) (7 6) (8 3))

((1 6) (2 1) (3 5) (4 2) (5 8) (6 3) (7 7) (8 4))

((1 6) (2 2) (3 7) (4 1) (5 3) (6 5) (7 8) (8 4))

((1 6) (2 2) (3 7) (4 1) (5 4) (6 8) (7 5) (8 3))

((1 6) (2 3) (3 1) (4 7) (5 5) (6 8) (7 2) (8 4))

((1 6) (2 3) (3 1) (4 8) (5 4) (6 2) (7 7) (8 5))

((1 6) (2 3) (3 1) (4 8) (5 5) (6 2) (7 4) (8 7))

((1 6) (2 3) (3 5) (4 7) (5 1) (6 4) (7 2) (8 8))

((1 6) (2 3) (3 5) (4 8) (5 1) (6 4) (7 2) (8 7))

((1 6) (2 3) (3 7) (4 2) (5 4) (6 8) (7 1) (8 5))

((1 6) (2 3) (3 7) (4 2) (5 8) (6 5) (7 1) (8 4))

((1 6) (2 3) (3 7) (4 4) (5 1) (6 8) (7 2) (8 5))

((1 6) (2 4) (3 1) (4 5) (5 8) (6 2) (7 7) (8 3))

((1 6) (2 4) (3 2) (4 8) (5 5) (6 7) (7 1) (8 3))

((1 6) (2 4) (3 7) (4 1) (5 3) (6 5) (7 2) (8 8))

((1 6) (2 4) (3 7) (4 1) (5 8) (6 2) (7 5) (8 3))

((1 6) (2 8) (3 2) (4 4) (5 1) (6 7) (7 5) (8 3))

((1 7) (2 1) (3 3) (4 8) (5 6) (6 4) (7 2) (8 5))

((1 7) (2 2) (3 4) (4 1) (5 8) (6 5) (7 3) (8 6))

((1 7) (2 2) (3 6) (4 3) (5 1) (6 4) (7 8) (8 5))

((1 7) (2 3) (3 1) (4 6) (5 8) (6 5) (7 2) (8 4))

((1 7) (2 3) (3 8) (4 2) (5 5) (6 1) (7 6) (8 4))

((1 7) (2 4) (3 2) (4 5) (5 8) (6 1) (7 3) (8 6))

((1 7) (2 4) (3 2) (4 8) (5 6) (6 1) (7 3) (8 5))

((1 7) (2 5) (3 3) (4 1) (5 6) (6 8) (7 2) (8 4))

((1 8) (2 2) (3 4) (4 1) (5 7) (6 5) (7 3) (8 6))

((1 8) (2 2) (3 5) (4 3) (5 1) (6 7) (7 4) (8 6))

((1 8) (2 3) (3 1) (4 6) (5 2) (6 5) (7 7) (8 4))

((1 8) (2 4) (3 1) (4 3) (5 6) (6 2) (7 7) (8 5))