骑士之旅回溯 Lisp

Question

我在为这个程序生成正确的输出时遇到了一些问题。我的输出几乎是正确的，但缺少一些步骤。我的代码如下：

(defun kt (x y m n)                       ;set the board
  (setq totalmoves (* m n))     ;find the total moves
  (setq steps 1)                         ;count steps
  (setq lst (list (list x y)))  ;list visited with initial points
  (findPath x y totalmoves steps m n lst)       ;start tour with initial points
)

(defun findPath (x y totalMoves steps m n lst)
  (cond
  ((null lst) NIL)
  ((= steps totalMoves) lst)                ;if steps equals than total moves, then solution is complete
  ;try to solve the rest recursively
  ;1- down and right
  ((canMove (+ x 2) (+ y 1) m n lst)
    (findPath (+ x 2) (+ y 1) totalMoves (+ steps 1) m n (appendList (+ x 2)        (+ y 1) lst))

)
;2- right and down
((canMove (+ x 1) (+ y 2) m n lst)
     (findPath (+ x 1) (+ y 2) totalMoves (+ steps 1) m n (appendList (+ x 1) (+ y 2) lst))

)
;3- right ups
((canMove (- x 1) (+ y 2) m n lst)
     (findPath (- x 1) (+ y 2) totalMoves (+ steps 1) m n (appendList(- x 1) (+ y 2) lst))

)
;4- up and right
((canMove(- x 2) (+ y 1) m n lst)
     (findPath(- x 2) (+ y 1) totalMoves (+ steps 1) m n (appendList(- x 2) (+ y 1) lst))
)
;5 - up and left
((canMove(- x 2) (- y 1) m n lst)
     (findPath(- x 2) (- y 1) totalMoves (+ steps 1) m n (appendList(- x 2) (- y 1) lst))
)
;6- left and up 
((canMove(- x 1) (- y 2) m n lst)
     (findPath(- x 1) (- y 2) totalMoves (+ steps 1) m n (appendList(- x 1) (- y 2) lst))
)
;7- left and down
((canMove(+ x 1) (- y 2) m n lst)
     (findPath(+ x 1) (- y 2) totalMoves (+ steps 1) m n (appendList(+ x 1) (- y 2) lst))
)
;8- down and left
((canMove(+ x 2) (- y 1) m n lst)
     (findPath(+ x 2) (- y 1) totalMoves (+ steps 1) m n (appendList(+ x 2) (- y 1) lst))
)
(t 
 (findPath (car(car(reverse lst))) (car(cdr(car(reverse lst)))) totalMoves steps m n (reverse(cdr (reverse lst))))
  )
)
)

(defun appendList (x y lst)
  (setq lst (reverse(append (list (list x y)) (reverse lst))))
)

(defun check-visited (x y lst)
  (cond
    ((null lst) 1)              ;if nth else to check in list
    ((equal (list x y) (car lst)) NIL)    ;check if curr is visited
    ((check-visited x y (cdr lst)))        ;recurse
  )
)

(defun canMove (x y m n lst)
  (if (and (<= 1 x)         ;for the correct state, all conditions below must be met          
       (<= x m)    ;height is more than or equal to x
       (<= 1 y)
       (<= y n)     ;width is more than or equal to y
       (equal (check-visited x y lst) 1)
  ) 
  1 NIL ;if all above conds are true, return true else return nil
)
)

测试代码为

kt 1 1 5 5

输出为((1 1) (3 2) (5 3) (4 5) (2 4) (1 2) (3 3) (5 4) (3 5) (1 4) (2 2) (4 3) (5 5) (3 4) (1 5) (2 3) (4 4) (2 5) (1 3) (2 1) (4 2))

这里列出了 21 个步骤，但应该有 25 个。

Answer 1

您的方法是不正确的，因为函数 findPath 不会在某个位置尝试所有可能的移动，但是，使用 cond，只会尝试 first 可能的移动（在 cond 中，第一个非 nil 分支被执行，语句通过返回对应的 findPath 调用的值来终止）。因此，您的函数只产生没有回溯的最长行程，正好是 21 步。

为了获得正确的解决方案，您必须尝试所有可能的移动，返回第一个通过对 findPath 的递归调用产生的移动正确的移动次数。在 Common Lisp 中，这可以通过使用 or 和 and 运算符来完成：

or，有 n 个操作数，returns 第一个操作数不是 nil 的值，如果存在，否则它 returns nil：所以如果我们安排放入一个 or 所有 findPath 的递归调用，如果其中一个 returns正确的最终值 or 表达式终止返回该值；
and returns nil 如果它的任何一个操作数是nil，否则，如果它们都不是nil , 它 returns 最后一个操作数的值。所以我们可以通过首先检查移动是否可能来使用它，如果是，则通过递归调用 findPath 来执行移动。如果调用returnsnil那么那一步棋没有用，否则我们已经找到了正确的游。

这是新函数：

(defun findPath (x y totalMoves steps m n lst)
  (if (= steps totalMoves)
      lst           ; if the steps are equal to total moves, then a solution is found
                    ; else try recursively all the possible moves from x y
                    ; 1- down and right
      (or (and (canMove (+ x 2) (+ y 1) m n lst)
               (findPath (+ x 2) (+ y 1) totalMoves (+ steps 1) m n (appendList (+ x 2) (+ y 1) lst)))
                    ; 2- right and down
          (and (canMove (+ x 1) (+ y 2) m n lst)
               (findPath (+ x 1) (+ y 2) totalMoves (+ steps 1) m n (appendList (+ x 1) (+ y 2) lst)))
                    ; 3- right ups
          (and (canMove (- x 1) (+ y 2) m n lst)
               (findPath (- x 1) (+ y 2) totalMoves (+ steps 1) m n (appendList (- x 1) (+ y 2) lst)))
                    ; 4- up and right
          (and (canMove (- x 2) (+ y 1) m n lst)
               (findPath (- x 2) (+ y 1) totalMoves (+ steps 1) m n (appendList (- x 2) (+ y 1) lst)))
                    ; 5 - up and left
          (and (canMove (- x 2) (- y 1) m n lst)
               (findPath (- x 2) (- y 1) totalMoves (+ steps 1) m n (appendList (- x 2) (- y 1) lst)))
                    ; 6- left and up 
          (and (canMove (- x 1) (- y 2) m n lst)
               (findPath (- x 1) (- y 2) totalMoves (+ steps 1) m n (appendList (- x 1) (- y 2) lst)))
                    ; 7- left and down
          (and (canMove (+ x 1) (- y 2) m n lst)
               (findPath (+ x 1) (- y 2) totalMoves (+ steps 1) m n (appendList (+ x 1) (- y 2) lst)))
                    ; 8- down and left
          (and (canMove (+ x 2) (- y 1) m n lst)
               (findPath (+ x 2) (- y 1) totalMoves (+ steps 1) m n (appendList (+ x 2) (- y 1) lst))))))

最后，关于代码的几点说明。

不要使用setq初始化之前未声明的变量

let可以用来声明和初始化局部变量，所以函数kt可以这样定义：

(defun kt (x y m n)                            ; set the board
  (let ((totalmoves (* m n))                   ; find the total moves
        (steps 1)                              ; count steps
        (lst (list (list x y))))               ; list visited with initial points
    (findPath x y totalmoves steps m n lst)))  ; start tour with initial points

尽量保持代码简单

函数appendList是通过将一个单元素列表追加到另一个单元素列表的反面，然后反转结果来定义的。这相当于简单地将第一个列表附加到第二个列表，即：

(defun appendList (x y lst)
  (append lst (list (list x y))))

使用generalized booleans简化条件

例如，函数 check-visited 和 canMove 可以集成到一个更简单的函数中：

(defun canMove (x y m n lst)
  (and (<= 1 x m)      ;for the correct state, all conditions below must be met          
       (<= 1 y n)
       (not (member (list x y) lst :test 'equal))))

尝试分解你的代码，或者在不必要的时候不要重复类似的代码

函数findPath有很多重复，可以使用loop消除（thereis等同于or loop):

(defun findPath (x y totalMoves steps m n lst)
  (if (= steps totalMoves)
      lst 
      (loop for (x-inc y-inc) in '((+2 +1) (+1 +2) (-1 +2) (-2 +1) (-2 -1) (-1 -2) (+1 -2) (+2 -1))
        for x1 = (+ x x-inc)
        for y1 = (+ y y-inc)
        thereis (and (canMove x1 y1 m n lst)
                     (findPath x1 y1 totalMoves (1+ steps) m n (appendList x1 y1 lst))))))

使用所用语言的典型约定

在 Common Lisp 中，避免了驼峰式大小写，更喜欢用破折号分隔的名称和动词的经典表示法，例如 find-path 而不是 findPath，或 can-move 而不是 canMove，等等

骑士之旅回溯 Lisp

Knights tour backtracking Lisp

lisp

backtracking

knights-tour