lisp - 骑士之旅回溯 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，只尝试 第一个 可能的移动(在 cond 中，执行第一个非 nil 分支并通过返回对应的值终止语句 findPath称呼)。因此，您的函数仅产生没有回溯的最长行程，正好是 21 步。

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

1. or，有n个操作数，返回第一个不为nil的操作数的值，如果存在，否则返回nil:所以如果我们安排放入或所有findPath的递归调用，如果其中一个返回正确的最终值或表达式终止返回该值；

2. and 返回 nil 如果它的任何操作数是 nil，否则，如果它们都不是 nil ，它返回最后一个操作数的值。所以我们可以通过首先检查移动是否可能来使用它，如果是，则通过递归调用 findPath 来执行移动。如果调用返回 nil，则该移动没有用，否则我们找到了正确的路线。

这是新功能:

(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 相当于 loop 中的 or):

(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 等