Решение головоломок на Lisp

Узнай цену своей работы

Формулировка задачи:

Помогите с решением следующей задачи. Используя рекурсии, на языке Lisp решить головоломку. Есть восемь перенумерованных пней. На пнях 1 и 3 сидят кролики, на пнях 6 и 8 — белки. И белки, и кролики хотят обменяться пнями: белки желают сидеть на местах кроликов, а кролики — на местах белок. Попасть на новое место они могут, прыгая с пня на пень по следующим правилам: 1. прыгать с пня на пень можно только по тем линиям, которые показаны на рисунке; каждый зверек может делать несколько прыжков кряду; 2. два зверька на одном пне поместиться не могут, поэтому прыгать можно только на свободный пень. Нужно найти минимальную последовательность прыжков, для достижения цели.

Решение задачи: «Решение головоломок на Lisp»

textual
Листинг программы
(setq s '(1 3 6 8))
(setq te '((1 5) (1 7) (2 6) (2 8) (3 4) (3 7) (4 3) (4 8) (5 1) (5 6) (6 2) (6 5) (7 1) (7 3) (8 4) (8 2))) 
 
(defun temp(st tr)
    (labels
        ((appl(state tree n)
            (cond ((null state) nil)
            ((equal (car state) (car (car tree))) (append (list (car tree)) (appl state (cdr tree) (- n 1))))
            ((= n 0) (appl (cdr state) tr 2))
            (t (appl state (cdr tree) n))))
    )
    (appl st tr 2)
    )
)
 
(defun safe (state tree)
        (cond ((null tree) nil)
            ((not (null (member (car (last (car tree))) state))) (safe state (cdr tree)))
            (t (append (list (car tree)) (safe state (cdr tree))))
        )
)
 
(print (safe s (temp s te))) --->((1 5) (1 7) (3 4) (3 7) (6 2) (6 5) (8 4) (8 2))

Оцени полезность:

6   голосов , оценка 4 из 5