(defstruct estado
  ml cl ; misioneros y caníbales en la izquierda
  mr cr ; misioneros y caníbales en la derecha
  side ; 0 = bote a la izquierda, 1 = derecha
  camino) ; lista de pasos
 
(defun estado-valido-p (st)
  (let ((ml (estado-ml st))
        (cl (estado-cl st))
        (mr (estado-mr st))
        (cr (estado-cr st)))
    (and (>= ml 0) (<= ml 3)
         (>= cl 0) (<= cl 3)
         (>= mr 0) (<= mr 3)
         (>= cr 0) (<= cr 3)
         (or (= ml 0) (>= ml cl))
         (or (= mr 0) (>= mr cr)))))
 
(defun mover (st m c)
  (let* ((ml (estado-ml st))
         (cl (estado-cl st))
         (mr (estado-mr st))
         (cr (estado-cr st))
         (side (estado-side st)))
    (cond
      ((= side 0)
       (make-estado :ml (- ml m) :cl (- cl c)
                    :mr (+ mr m) :cr (+ cr c)
                    :side 1
                    :camino (append (estado-camino st)
                                    (list (format nil "~dM~dC ->" m c)))))
      (t
       (make-estado :ml (+ ml m) :cl (+ cl c)
                    :mr (- mr m) :cr (- cr c)
                    :side 0
                    :camino (append (estado-camino st)
                                    (list (format nil "~dM~dC <-" m c))))))))
 
(defun iguales (a b)
  (and (= (estado-ml a) (estado-ml b))
       (= (estado-cl a) (estado-cl b))
       (= (estado-mr a) (estado-mr b))
       (= (estado-cr a) (estado-cr b))
       (= (estado-side a) (estado-side b))))
 
(defun repetido-p (nuevo camino)
  (some (lambda (e) (iguales e nuevo)) camino))
 
(defparameter *viajes*
  '((2 0) (0 2) (1 1) (1 0) (0 1)))
 
(defun resolver (estado final camino)
  (when (iguales estado final)
    (push estado camino)
    (mostrar-solucion (reverse camino))
    (return-from resolver))
 
  (dolist (v *viajes*)
    (let ((m (first v))
          (c (second v)))
      (when (and (<= (+ m c) 2) (> (+ m c) 0))
        (let ((nuevo (mover estado m c)))
          (when (and (estado-valido-p nuevo)
                     (not (repetido-p nuevo camino)))
            (resolver nuevo final (cons estado camino))))))))
 
(defun personas (m c)
  (concatenate 'string
               (make-string m :initial-element #\M)
               (make-string c :initial-element #\C)))
 
(defun lado-a-string (m c)
  (format nil "[~a]" (personas m c)))
 
(defun mostrar-paso (anterior actual)
  (let ((ml (estado-ml anterior))
        (cl (estado-cl anterior))
        (mr (estado-mr anterior))
        (cr (estado-cr anterior))
        (side (estado-side anterior))
        (ml2 (estado-ml actual))
        (cl2 (estado-cl actual))
        (mr2 (estado-mr actual))
        (cr2 (estado-cr actual))
        (side2 (estado-side actual)))
 
    ;; Determinar quién cruzó
    (let* ((dm (- ml ml2))
           (dc (- cl cl2))
           (m (abs dm))
           (c (abs dc))
           (cruce (personas m c)))
      (format t "~%Paso ~a (antes de cruzar):~%" (+ 1 (length (estado-camino anterior))))
      (if (= side 0)
          (format t "~a B ~~~~~~ []~%" (lado-a-string ml cl))
          (format t "~a ~~~~~~ B ~a~%" (lado-a-string ml cl) (lado-a-string mr cr)))
      (format t "Cruzando con: ~a~%" cruce)
      (format t "Paso ~a (después de cruzar):~%" (+ 1 (length (estado-camino anterior))))
      (if (= side2 0)
          (format t "~a B ~~~~~~ []~%" (lado-a-string ml2 cl2))
          (format t "~a ~~~~~~ B ~a~%" (lado-a-string ml2 cl2) (lado-a-string mr2 cr2))))))
 
(defun mostrar-solucion (camino)
  (format t "~%====================================~%") ;traviesos
  (format t "Solución en ~d pasos~%" (length (estado-camino (car (last camino)))))
  (loop for (a b) on camino while b do
        (mostrar-paso a b))
  (format t "~%====================================~%"))
 
(defun main ()
  (let ((inicio (make-estado :ml 3 :cl 3 :mr 0 :cr 0 :side 0 :camino '()))
        (fin (make-estado :ml 0 :cl 0 :mr 3 :cr 3 :side 1 :camino '())))
    (resolver inicio fin '())))
 
(main)

KGRlZnN0cnVjdCBlc3RhZG8KICBtbCBjbCA7IG1pc2lvbmVyb3MgeSBjYW7DrWJhbGVzIGVuIGxhIGl6cXVpZXJkYQogIG1yIGNyIDsgbWlzaW9uZXJvcyB5IGNhbsOtYmFsZXMgZW4gbGEgZGVyZWNoYQogIHNpZGUgOyAwID0gYm90ZSBhIGxhIGl6cXVpZXJkYSwgMSA9IGRlcmVjaGEKICBjYW1pbm8pIDsgbGlzdGEgZGUgcGFzb3MKIAooZGVmdW4gZXN0YWRvLXZhbGlkby1wIChzdCkKICAobGV0ICgobWwgKGVzdGFkby1tbCBzdCkpCiAgICAgICAgKGNsIChlc3RhZG8tY2wgc3QpKQogICAgICAgIChtciAoZXN0YWRvLW1yIHN0KSkKICAgICAgICAoY3IgKGVzdGFkby1jciBzdCkpKQogICAgKGFuZCAoPj0gbWwgMCkgKDw9IG1sIDMpCiAgICAgICAgICg+PSBjbCAwKSAoPD0gY2wgMykKICAgICAgICAgKD49IG1yIDApICg8PSBtciAzKQogICAgICAgICAoPj0gY3IgMCkgKDw9IGNyIDMpCiAgICAgICAgIChvciAoPSBtbCAwKSAoPj0gbWwgY2wpKQogICAgICAgICAob3IgKD0gbXIgMCkgKD49IG1yIGNyKSkpKSkKIAooZGVmdW4gbW92ZXIgKHN0IG0gYykKICAobGV0KiAoKG1sIChlc3RhZG8tbWwgc3QpKQogICAgICAgICAoY2wgKGVzdGFkby1jbCBzdCkpCiAgICAgICAgIChtciAoZXN0YWRvLW1yIHN0KSkKICAgICAgICAgKGNyIChlc3RhZG8tY3Igc3QpKQogICAgICAgICAoc2lkZSAoZXN0YWRvLXNpZGUgc3QpKSkKICAgIChjb25kCiAgICAgICgoPSBzaWRlIDApCiAgICAgICAobWFrZS1lc3RhZG8gOm1sICgtIG1sIG0pIDpjbCAoLSBjbCBjKQogICAgICAgICAgICAgICAgICAgIDptciAoKyBtciBtKSA6Y3IgKCsgY3IgYykKICAgICAgICAgICAgICAgICAgICA6c2lkZSAxCiAgICAgICAgICAgICAgICAgICAgOmNhbWlubyAoYXBwZW5kIChlc3RhZG8tY2FtaW5vIHN0KQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAobGlzdCAoZm9ybWF0IG5pbCAifmRNfmRDIC0+IiBtIGMpKSkpKQogICAgICAodAogICAgICAgKG1ha2UtZXN0YWRvIDptbCAoKyBtbCBtKSA6Y2wgKCsgY2wgYykKICAgICAgICAgICAgICAgICAgICA6bXIgKC0gbXIgbSkgOmNyICgtIGNyIGMpCiAgICAgICAgICAgICAgICAgICAgOnNpZGUgMAogICAgICAgICAgICAgICAgICAgIDpjYW1pbm8gKGFwcGVuZCAoZXN0YWRvLWNhbWlubyBzdCkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKGxpc3QgKGZvcm1hdCBuaWwgIn5kTX5kQyA8LSIgbSBjKSkpKSkpKSkKIAooZGVmdW4gaWd1YWxlcyAoYSBiKQogIChhbmQgKD0gKGVzdGFkby1tbCBhKSAoZXN0YWRvLW1sIGIpKQogICAgICAgKD0gKGVzdGFkby1jbCBhKSAoZXN0YWRvLWNsIGIpKQogICAgICAgKD0gKGVzdGFkby1tciBhKSAoZXN0YWRvLW1yIGIpKQogICAgICAgKD0gKGVzdGFkby1jciBhKSAoZXN0YWRvLWNyIGIpKQogICAgICAgKD0gKGVzdGFkby1zaWRlIGEpIChlc3RhZG8tc2lkZSBiKSkpKQogCihkZWZ1biByZXBldGlkby1wIChudWV2byBjYW1pbm8pCiAgKHNvbWUgKGxhbWJkYSAoZSkgKGlndWFsZXMgZSBudWV2bykpIGNhbWlubykpCiAKKGRlZnBhcmFtZXRlciAqdmlhamVzKgogICcoKDIgMCkgKDAgMikgKDEgMSkgKDEgMCkgKDAgMSkpKQogCihkZWZ1biByZXNvbHZlciAoZXN0YWRvIGZpbmFsIGNhbWlubykKICAod2hlbiAoaWd1YWxlcyBlc3RhZG8gZmluYWwpCiAgICAocHVzaCBlc3RhZG8gY2FtaW5vKQogICAgKG1vc3RyYXItc29sdWNpb24gKHJldmVyc2UgY2FtaW5vKSkKICAgIChyZXR1cm4tZnJvbSByZXNvbHZlcikpCiAKICAoZG9saXN0ICh2ICp2aWFqZXMqKQogICAgKGxldCAoKG0gKGZpcnN0IHYpKQogICAgICAgICAgKGMgKHNlY29uZCB2KSkpCiAgICAgICh3aGVuIChhbmQgKDw9ICgrIG0gYykgMikgKD4gKCsgbSBjKSAwKSkKICAgICAgICAobGV0ICgobnVldm8gKG1vdmVyIGVzdGFkbyBtIGMpKSkKICAgICAgICAgICh3aGVuIChhbmQgKGVzdGFkby12YWxpZG8tcCBudWV2bykKICAgICAgICAgICAgICAgICAgICAgKG5vdCAocmVwZXRpZG8tcCBudWV2byBjYW1pbm8pKSkKICAgICAgICAgICAgKHJlc29sdmVyIG51ZXZvIGZpbmFsIChjb25zIGVzdGFkbyBjYW1pbm8pKSkpKSkpKQogCihkZWZ1biBwZXJzb25hcyAobSBjKQogIChjb25jYXRlbmF0ZSAnc3RyaW5nCiAgICAgICAgICAgICAgIChtYWtlLXN0cmluZyBtIDppbml0aWFsLWVsZW1lbnQgI1xNKQogICAgICAgICAgICAgICAobWFrZS1zdHJpbmcgYyA6aW5pdGlhbC1lbGVtZW50ICNcQykpKQogCihkZWZ1biBsYWRvLWEtc3RyaW5nIChtIGMpCiAgKGZvcm1hdCBuaWwgIlt+YV0iIChwZXJzb25hcyBtIGMpKSkKIAooZGVmdW4gbW9zdHJhci1wYXNvIChhbnRlcmlvciBhY3R1YWwpCiAgKGxldCAoKG1sIChlc3RhZG8tbWwgYW50ZXJpb3IpKQogICAgICAgIChjbCAoZXN0YWRvLWNsIGFudGVyaW9yKSkKICAgICAgICAobXIgKGVzdGFkby1tciBhbnRlcmlvcikpCiAgICAgICAgKGNyIChlc3RhZG8tY3IgYW50ZXJpb3IpKQogICAgICAgIChzaWRlIChlc3RhZG8tc2lkZSBhbnRlcmlvcikpCiAgICAgICAgKG1sMiAoZXN0YWRvLW1sIGFjdHVhbCkpCiAgICAgICAgKGNsMiAoZXN0YWRvLWNsIGFjdHVhbCkpCiAgICAgICAgKG1yMiAoZXN0YWRvLW1yIGFjdHVhbCkpCiAgICAgICAgKGNyMiAoZXN0YWRvLWNyIGFjdHVhbCkpCiAgICAgICAgKHNpZGUyIChlc3RhZG8tc2lkZSBhY3R1YWwpKSkKIAogICAgOzsgRGV0ZXJtaW5hciBxdWnDqW4gY3J1esOzCiAgICAobGV0KiAoKGRtICgtIG1sIG1sMikpCiAgICAgICAgICAgKGRjICgtIGNsIGNsMikpCiAgICAgICAgICAgKG0gKGFicyBkbSkpCiAgICAgICAgICAgKGMgKGFicyBkYykpCiAgICAgICAgICAgKGNydWNlIChwZXJzb25hcyBtIGMpKSkKICAgICAgKGZvcm1hdCB0ICJ+JVBhc28gfmEgKGFudGVzIGRlIGNydXphcik6fiUiICgrIDEgKGxlbmd0aCAoZXN0YWRvLWNhbWlubyBhbnRlcmlvcikpKSkKICAgICAgKGlmICg9IHNpZGUgMCkKICAgICAgICAgIChmb3JtYXQgdCAifmEgQiB+fn5+fn4gW11+JSIgKGxhZG8tYS1zdHJpbmcgbWwgY2wpKQogICAgICAgICAgKGZvcm1hdCB0ICJ+YSB+fn5+fn4gQiB+YX4lIiAobGFkby1hLXN0cmluZyBtbCBjbCkgKGxhZG8tYS1zdHJpbmcgbXIgY3IpKSkKICAgICAgKGZvcm1hdCB0ICJDcnV6YW5kbyBjb246IH5hfiUiIGNydWNlKQogICAgICAoZm9ybWF0IHQgIlBhc28gfmEgKGRlc3B1w6lzIGRlIGNydXphcik6fiUiICgrIDEgKGxlbmd0aCAoZXN0YWRvLWNhbWlubyBhbnRlcmlvcikpKSkKICAgICAgKGlmICg9IHNpZGUyIDApCiAgICAgICAgICAoZm9ybWF0IHQgIn5hIEIgfn5+fn5+IFtdfiUiIChsYWRvLWEtc3RyaW5nIG1sMiBjbDIpKQogICAgICAgICAgKGZvcm1hdCB0ICJ+YSB+fn5+fn4gQiB+YX4lIiAobGFkby1hLXN0cmluZyBtbDIgY2wyKSAobGFkby1hLXN0cmluZyBtcjIgY3IyKSkpKSkpCiAKKGRlZnVuIG1vc3RyYXItc29sdWNpb24gKGNhbWlubykKICAoZm9ybWF0IHQgIn4lPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09fiUiKSA7dHJhdmllc29zCiAgKGZvcm1hdCB0ICJTb2x1Y2nDs24gZW4gfmQgcGFzb3N+JSIgKGxlbmd0aCAoZXN0YWRvLWNhbWlubyAoY2FyIChsYXN0IGNhbWlubykpKSkpCiAgKGxvb3AgZm9yIChhIGIpIG9uIGNhbWlubyB3aGlsZSBiIGRvCiAgICAgICAgKG1vc3RyYXItcGFzbyBhIGIpKQogIChmb3JtYXQgdCAifiU9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT1+JSIpKQogCihkZWZ1biBtYWluICgpCiAgKGxldCAoKGluaWNpbyAobWFrZS1lc3RhZG8gOm1sIDMgOmNsIDMgOm1yIDAgOmNyIDAgOnNpZGUgMCA6Y2FtaW5vICcoKSkpCiAgICAgICAgKGZpbiAobWFrZS1lc3RhZG8gOm1sIDAgOmNsIDAgOm1yIDMgOmNyIDMgOnNpZGUgMSA6Y2FtaW5vICcoKSkpKQogICAgKHJlc29sdmVyIGluaWNpbyBmaW4gJygpKSkpCiAKKG1haW4p