Решение логических задач на Lisp

;Функция opposite позволяет менять местоположение путника
(defun opposite(side)
    (cond 
        ((equal side 'e) 'w)
        ((equal side 'w) 'e)
    )
)
 
;Функция takes позволяет перевозить в лодке пассажиров, но генерирует много ненужных последовательностей
(defun takes (state n1 n2 n3)
    (labels ((test(state num1 num2 num3 e boat)
                (cond
                    ((null state) nil)
                    ((= e 0)(if 
                        (and (> num1 -1)(> num2 -1)(> num3 -1)) 
                                (if (and 
                                    (equal (nth num1 state) (nth num2 state)) 
                                    (equal (nth num1 state) (nth num3 state)) 
                                    (equal (nth num1 state) (car (last state)))) 
                                        (test state num1 num2 num3 (+ e 1) boat)
                                        nil
                                )
                    ))
                    ((= 0 num1)(append (list(opposite (nth 0 state))) (test (cdr state) (setf num1 -1) (- num2 1)(- num3 1) e (- boat 1))))
                    ((= 0 num2)(append (list(opposite (nth 0 state))) (test (cdr state) (- num1 1) (setf num2 -1)(- num3 1) e (- boat 1))))
                    ((= 0 num3)(append (list(opposite (nth 0 state))) (test (cdr state) (- num1 1) (- num2 1)(setf num3 -1) e (- boat 1))))
                    ((= 0 boat)(append (list(opposite (nth 0 state)))))
                    (t (append (list (car state)) (test (cdr state) (- num1 1)(- num2 1)(- num3 1) e (- boat 1))))
                )
            )
        )
    (test state n1 n2 n3 0 (- (length state) 1))
    )
)
 
;Функция testiter перебирает всевозможные комбинации из трех чисел. Первым параметром приходит тот, кто перевозит - он не изменяется.
(defun testiter (state n n1 n2)
    (cond   ((> n2 (- (length state) 2)) nil)
            ((> n1 (- (length state) 2)) (append (list (takes state n n1 n2)) (testiter state n 0 (+ n2 1))))
            (t (append (list (takes state n n1 n2))(testiter state n (+ n1 1) n2)))
    )
)
 
;Функция del удаляет одинаковые комбинации ходов.
(defun del(lst)
    (labels(
            (temp (a b len)
                (cond 
                    ((null a) nil)
                    ((equal (car a) (car b))(temp (cdr a) (cddr a) (- (length lst) 1)))
                    ((= len 0) (append (list (car a))(temp (cdr a) (cddr a) (- (length lst) 1))))
                    (t (temp a (cdr b) (- len 1)))
                )
            )
        )
        (temp lst (cdr lst) (- (length lst) 1))
    )
)
 
; Функции *-side возвращают, где находится тот или иной путник. 
(defun r1-side (state)(nth 0 state)) 
(defun r2-side (state)(nth 1 state)) 
(defun r3-side (state)(nth 2 state)) 
(defun r4-side (state)(nth 3 state)) 
(defun o1-side (state)(nth 4 state)) 
(defun o2-side (state)(nth 5 state)) 
(defun o3-side (state)(nth 6 state))
(defun o4-side (state)(nth 7 state)) 
(defun o4-side (state)(nth 8 state)) 
 
;Функция safe проверяет, можно ли сделать ход. Суть состоит в том, что происходит проверка, если рыцарь и оруженосец на разных берегах и какой-то рыцарь на берегу с этим оруженосцем.
(defun safe (state)
    (cond 
        ((and (or (equal (r2-side state) (o1-side state)) (equal (r3-side state) (o1-side state))(equal (r4-side state) (o1-side state)))(not (equal (r1-side state) (o1-side state)))) nil)
        ((and (or (equal (r1-side state) (o2-side state)) (equal (r3-side state) (o2-side state))(equal (r4-side state) (o2-side state)))(not (equal (r2-side state) (o2-side state)))) nil)
        ((and (or (equal (r2-side state) (o3-side state)) (equal (r1-side state) (o3-side state))(equal (r4-side state) (o3-side state)))(not (equal (r3-side state) (o3-side state)))) nil)
        ((and (or (equal (r2-side state) (o4-side state)) (equal (r3-side state) (o4-side state))(equal (r1-side state) (o4-side state)))(not (equal (r4-side state) (o4-side state)))) nil)
        (t state)
    )
)
 
;Функция checkSafe данная функция применяет функцию safe к каждому элементу списка
(defun checkSafe(lst)
    (cond ((null lst) nil)
        (t (append (list (safe (car lst))) (checkSafe (cdr lst))))
    )
)
 
;Функция pos_move возвращает ходы, которые применимы для входящего состояния
(defun pos_move(state)
    (del (append (remove 'NIL (checkSafe (del (testiter state 0 0 0))))
            (remove 'NIL (checkSafe (del (testiter state 1 0 0))))
            (remove 'NIL (checkSafe (del (testiter state 2 0 0))))
            (remove 'NIL (checkSafe (del (testiter state 3 0 0))))
            (remove 'NIL (checkSafe (del (testiter state 4 0 0))))
            (remove 'NIL (checkSafe (del (testiter state 5 0 0))))
            (remove 'NIL (checkSafe (del (testiter state 6 0 0))))
            (remove 'NIL (checkSafe (del (testiter state 7 0 0))))
        )
    )
)
 
;Функция checkGoal проверяет есть ли в списке возможных ходов, наше целевое значение, если да возвращает true, иначе nil
(defun checkGoal (state goal)
    (cond 
        ((null state) nil)
        ((equal (car state) goal) (car state))
        (t (checkGoal (cdr state) goal))
    )
)
 
;Функция checkWas проверяет есть ли в списке уже пройденных вершин, вершины из списка возможных ходов
(defun checkWas (st b)
    (labels
        ((temp (state been_list len)
            (cond
                ((null state) nil)
                ((null been_list) state)
                ((equal (car state) (car been_list)) (temp (cdr state) b (- (length b) 1)))
                ((= len 0) (append (list (car state)) (temp (cdr state) b (- (length b) 1))))
                (t (temp state (cdr been_list) (- len 1)))
            )
        ))
    (temp st b (- (length b) 1))
    )
)
 
 
;Функция path 
(defun path(state goal been_list)
    (cond 
        ((null state) nil)
        ((not (null (checkGoal been_list goal))) (reverse (cons (checkGoal state goal) been_list)))
        ((not (null (checkGoal state goal))) (reverse (cons (checkGoal state goal) been_list)))
        ((not (null (checkWas state been_list)))  
                (or 
                    (path (pos_move (car (checkWas state been_list))) goal (cons (car (checkWas state been_list)) been_list))
                    (path (cdr (checkWas state been_list)) goal been_list)
                )
        )
    )
)
 
(print (path '((w w w w w w w w w)) '(e e e e e e e e e) nil))