Ric*_*erg 0 recursion common-lisp n-queens
更新:代码应该现在编译,没有错误或警告.对前一个抱歉.我现在遇到的问题是运行时(或任何其他整数)
(NxNqueen-solver 10)
函数getqueencol将返回nil,因为首先在棋盘上没有皇后,因此在皇后可以放置(=数字nil),因为tcol将为零.我想这会发生在每次没有女王作为参数传递给女王可以放置在这里的函数时.
请分享一些有关如何解决此问题的建议.先感谢您.
这是代码
(defvar *board* (make-array '(10 10) :initial-element nil))
(defun getqueencol (row n)
"Traverses through the columns of a certain row
and returns the column index of the queen."
(loop for i below n
do (if (aref *board* row i)
(return-from getqueencol i))))
(defun print-board (n)
"Prints out the solution, e.g. (1 4 2 5 3),
where 1 denotes that there is a queen at the first
column of the first row, and so on."
(let ((solutionlist (make-list n)))
(loop for row below n
do (loop for col below n
do (when (aref *board* row col)
(setf (nth row solutionlist) col))))
(print solutionlist)))
(defun queen-can-be-placed-here (row col n)
"Returns t if (row,col) is a possible place to put queen, otherwise nil."
(loop for i below n
do (let ((tcol (getqueencol i n)))
(if (or (= col tcol) (= (abs (- row i)) (abs (- col tcol))))
(return-from queen-can-be-placed-here nil)))))
(defun backtracking (row n)
"Solves the NxN-queen problem with backtracking"
(if (< row n)
(loop for i below n
do (when (queen-can-be-placed-here row i n)
(setf (aref *board* row i) 't)
(return-from backtracking (backtracking (+ row 1) n))
(setf (aref *board* row i) 'nil))
(print-board n))))
(defun NxNqueen-solver (k)
"Main program for the function call to the recursive solving of the problem"
(setf *board* (make-array '(k k) :initial-element nil))
(backtracking 0 k))
你说你编译了你的代码.情况并非如此,因为那时您会看到编译器抱怨错误.您希望确保真正编译代码并更正代码,以便编译时不会出现错误和警告.
您可能希望摆脱代码中的错误/问题(请参阅Renzo的评论),然后查看算法问题.当代码包含错误时,我很难理解算法问题.
SETQ 不引入变量,必须在某处定义变量
DEFVAR 在函数内部没有任何意义.
(let (x (sin a)) ...)肯定看起来像错了.语法LET需要绑定列表周围的一对括号.
RETURN-FROM将第一个参数作为要返回的现有块的名称.可选的第二个参数是返回值.获取正确的语法并从正确的块返回.
在调用中MAKE-ARRAY指定默认值:(make-array ... :initial-element nil)否则不清楚它是什么.
变量*board*未定义
样式
in LOOP: for i to (1- n)更简单for i below n
你不需要引用NIL和T.
(if (eq foo t) ...)可能更简单(if foo ...).特别是如果值foo是NIL或者T.
(if foo (progn ...)) 很简单 (when foo ...)
我不知道你在做什么声称你的代码编译.它不编译.
每个函数都有编译器警告.您应该检查编译器警告并解决问题.
(defun getqueencol (row)
"Traverses through the columns of a certain row
and returns the column index of the queen."
(loop for i below n
do (if (aref board row i)
(return-from getqueencol i))))
编译器抱怨:
;;;*** Warning in GETQUEENCOL: N assumed special
;;;*** Warning in GETQUEENCOL: BOARD assumed special
在哪里n定义？board来自哪里？
(defun print-board (board)
"Prints out the solution, e.g. (1 4 2 5 3),
where 1 denotes that there is a queen at the first
column of the first row, and so on."
(let (solutionlist)
(setq solutionlist (make-list n)))
(loop for row below n
do (loop for col below n
do (when (aref board row col)
(setf (nth row solutionlist) col))))
(print solutionlist))
该LET是没有意义的.(let (foo) (setq foo bar) ...)是(let ((foo bar)) ...).
为什么没有定义解决方案列表？看看LET......它没有意义.
n来自哪里？
(defun queen-can-be-placed-here (row col)
"Returns t if (row,col) is a possible place to put queen, otherwise nil."
(loop for i below n
do (let (tcol)
(setq tcol (getqueencol i)))
(if (or (= col tcol) (= (abs (- row i)) (abs (- col tcol))))
(return-from queen-can-be-placed-here nil))))
哪里n来的？该LET是没有意义的.
(defun backtracking (row)
"Solves the NxN-queen problem with backtracking"
(if (< row n)
(loop for i below n
do (when (queen-can-be-placed-here row i)
(setf (aref board row i) 't)
(return-from backtracking (backtracking (+ row 1)))
(setf (aref board row i) 'nil))
(print-board board))))
n来自哪里？在哪里board定义？
(defun NxNqueen-solver (k)
"Main program for the function call to the recursive solving of the problem"
(let (n board)
(setq n k)
(setq board (make-array '(k k) :initial-element nil)))
(backtracking 0))
为什么setq在你有的时候使用let？局部变量n和board未使用.
MAKE-ARRAY 需要一个数字列表,而不是符号列表.
我建议你使用基本的Lisp介绍(Common Lisp:A Gentle Introduction to Symbolic Computation - 免费下载)和Lisp参考(CL Hyperspec).