1

我对 lisp 中的多个 if 语句有疑问。如果count不等于n我想继续使用letandif语句，否则我想做(= (abs (- row i))，如果那是t返回 nil。

但是，我发现无论何时count不是n我都会返回nil，因为progn总是返回块中的最后一行代码。请与我分享我如何编写程序，以便我只有在count不是n时才会返回nil任何or子句t。

(loop for i below n
      do (if (/= count n)
             (progn
               (let ((tcol (getqueencol i n)))
                 (if (or (= col tcol) (= (abs (- row i)) (abs (- col tcol))))
                     (return-from queen-can-be-placed-here nil))))
           (if (= (abs (- row i)))
               (return-from queen-can-be-placed-here nil))))

更新：

谢谢你的好回应。是的，确实我正在尝试解决 N 皇后难题 :P 我现在遇到的问题是，当行为空时，我的控制来确定是否将皇后放置在某个行和列上不起作用。那是因为getqueencol将nil在该行为空时返回，并且queen-can-be-placed-here其中会有一个(= nil NUMBER).

为了解决这个问题，我尝试创建一个计数变量queen-can-be-placed-here来知道一行是否为空，这将使我能够不调用getqueencol空行。问题是我不知道queen-can-be-placed-here当皇后被添加到空行时支票将如何进行。

这是到目前为止的代码： 

(defvar *board* (make-array '(5 5) :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."
  (let ((count 0))
    (loop for i below n  ;This is the block I added to keep track of if a     row is empty (count = n)
          do (if (not (aref *board* row i))   
                 (setf count (+ 1 count))))

    (loop for i below n
          do (if (/= count n)
                 (let ((tcol (getqueencol i n)))
                   (if (or (= col tcol) (= (abs (- row i)) (abs (- col     tcol))))
                       (return-from queen-can-be-placed-here nil)))
               (if (= (abs (- row i)))   ;Here is where I don't know what to check
                   (return-from queen-can-be-placed-here nil)))))

  (return-from queen-can-be-placed-here t))


(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)
                  (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 (list k k) :initial-element nil))
  (backtracking 0 k))
4

2 回答 2

2

我对 lisp 中的多个 if 语句有疑问。如果 count 不等于 n 我想继续使用 let 和 if 语句，否则我想做 (= (abs (- row i)) 并且如果那是 t 返回 nil。

一旦你开始在if的任一分支上有多个表单，使用cond通常会更清楚：

(cond
  ((/= n count)               ; if n is not count, then ...
   (let ...       
     (return-from ...)))      ; maybe return something
  ((= (abs (- row i)) ...)    ; else if |row-i] = ..., 
   (return-from ...)))        ; return nil

也就是说，您的if的then部分实际上并没有多个分支。无需将let包装在progn中。你可以这样做：

(if (/= count n)
    (let ((tcol (getqueencol i n)))
      (if (or (= col tcol) (= (abs (- row i)) (abs (- col tcol))))
          (return-from queen-can-be-placed-here nil)))
    (if (= (abs (- row i)))
        (return-from queen-can-be-placed-here nil)))

至于从if返回nil，有两件事需要考虑。您正在使用return-from，这意味着您正在执行非本地退出。虽然当test为 false 时表单表达式的值（如果 test then）为nil，但您永远不会对该值做任何事情。实际上，在没有其他部分的情况下，它是 Common Lisp 中相当常见的样式。也就是说，(when test then)等价于(if test then nil)和(if test then)。确实，这意味着（如果...）计算结果为nil，因此nil是let的值，因此也是progn的值，但您实际上并没有对progn的值做任何事情；它只是您在循环中评估的一种形式。

于 2015-09-25T13:00:02.830 回答
0

每次回溯调用都会尝试在每个可能的列上放置一个皇后。这意味着当您queen-can-be-placed-here在 row调用时row，您可以确保所有行（包括row后面的 row行）都是空的（回溯时会擦除棋盘）。

因此，您只需要通过查看具有较少行的棋盘子集来检查皇后是否可以正确放置在当前列col和当前列。row

             col
              v
           c0 v  c1

   r0      Q  -  -  -
   r1      -  -  Q  -
  row >>   -  ?  -  -
           -  -  -  -

仅当对于上述所有行，guetqueencol返回与直接对角线位置不同col或位于直接对角线位置的列时（使用 的计算abs），才可能存在皇后。所以你真的不需要计算任何东西，只需确保永远不会满足测试。

代码有一些小问题，比如变量名，所以一旦你确定一切都按预期工作，你可以在CodeReview上询问更多反馈，如果你愿意的话。

我认为适当的答案在以下剧透部分中。

（defun 皇后区可以放置在此处（第 n 行）
    “如果 (row,col) 是放置皇后的可能位置，则返回 t，否则为零。”
    （环形
       对于 r 下面的行
       对于 c = (getqueencol rn)
       从不（或（= col c）
                 (= (abs (- row r))
                    (绝对 (- col c))))))

于 2015-09-26T11:28:28.910 回答