(defstruct estado
  ml cl mr cr side camino)
 
(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 ((side (estado-side st)))
    (if (= side 0)
        (make-estado :ml (- (estado-ml st) m) :cl (- (estado-cl st) c)
                     :mr (+ (estado-mr st) m) :cr (+ (estado-cr st) c)
                     :side 1
                     :camino (append (estado-camino st) (list (format nil "~dM~dC ->" m c))))
        (make-estado :ml (+ (estado-ml st) m) :cl (+ (estado-cl st) c)
                     :mr (- (estado-mr st) m) :cr (- (estado-cr st) 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 historial)
  (some (lambda (e) (iguales e nuevo)) historial))
 
(defparameter *viajes* '((2 0) (0 2) (1 1) (1 0) (0 1)))
 
;; Contador global para identificar las soluciones
(defparameter *contador-soluciones* 0)
 
(defun resolver (estado final historial)
  (when (iguales estado final)
    (incf *contador-soluciones*)
    (mostrar-solucion (reverse (cons estado historial)) *contador-soluciones*)
    ;; NO ponemos return-from para que siga buscando más caminos
    (return-from resolver nil)) 
 
  (dolist (v *viajes*)
    (let* ((m (first v))
           (c (second v))
           (nuevo (mover estado m c)))
      (when (and (estado-valido-p nuevo)
                 (not (repetido-p nuevo historial)))
        (resolver nuevo final (cons estado historial))))))
 
(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 "[~3a]" (personas m c)))
 
(defun mostrar-paso (anterior actual)
  (let ((side (estado-side anterior))
        (movimiento (car (last (estado-camino actual)))))
    (format t "~%~a ~a ~a  | Acción: ~a" 
            (lado-a-string (estado-ml anterior) (estado-cl anterior))
            (if (= side 0) " B ~~~~   " "   ~~~~ B ")
            (lado-a-string (estado-mr anterior) (estado-cr anterior))
            movimiento)))
 
(defun mostrar-solucion (camino n)
  (format t "~%~%====================================")
  (format t "~%SOLUCIÓN NÚMERO ~d" n)
  (format t "~%====================================")
  (loop for (a b) on camino while b do (mostrar-paso a b))
  (let ((u (car (last camino))))
    (format t "~%~a    ~~~~ B  ~a  | ¡Llegaron!" 
            (lado-a-string (estado-ml u) (estado-cl u))
            (lado-a-string (estado-mr u) (estado-cr u)))))
 
(defun main ()
  (setf *contador-soluciones* 0) ; Reiniciar contador
  (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 '())
    (format t "~%~%Búsqueda finalizada. Se encontraron ~d soluciones.~%" *contador-soluciones*)))
 
(main)

KGRlZnN0cnVjdCBlc3RhZG8KICBtbCBjbCBtciBjciBzaWRlIGNhbWlubykKCihkZWZ1biBlc3RhZG8tdmFsaWRvLXAgKHN0KQogIChsZXQgKChtbCAoZXN0YWRvLW1sIHN0KSkgKGNsIChlc3RhZG8tY2wgc3QpKQogICAgICAgIChtciAoZXN0YWRvLW1yIHN0KSkgKGNyIChlc3RhZG8tY3Igc3QpKSkKICAgIChhbmQgKD49IG1sIDApICg8PSBtbCAzKSAoPj0gY2wgMCkgKDw9IGNsIDMpCiAgICAgICAgICg+PSBtciAwKSAoPD0gbXIgMykgKD49IGNyIDApICg8PSBjciAzKQogICAgICAgICAob3IgKD0gbWwgMCkgKD49IG1sIGNsKSkKICAgICAgICAgKG9yICg9IG1yIDApICg+PSBtciBjcikpKSkpCgooZGVmdW4gbW92ZXIgKHN0IG0gYykKICAobGV0ICgoc2lkZSAoZXN0YWRvLXNpZGUgc3QpKSkKICAgIChpZiAoPSBzaWRlIDApCiAgICAgICAgKG1ha2UtZXN0YWRvIDptbCAoLSAoZXN0YWRvLW1sIHN0KSBtKSA6Y2wgKC0gKGVzdGFkby1jbCBzdCkgYykKICAgICAgICAgICAgICAgICAgICAgOm1yICgrIChlc3RhZG8tbXIgc3QpIG0pIDpjciAoKyAoZXN0YWRvLWNyIHN0KSBjKQogICAgICAgICAgICAgICAgICAgICA6c2lkZSAxCiAgICAgICAgICAgICAgICAgICAgIDpjYW1pbm8gKGFwcGVuZCAoZXN0YWRvLWNhbWlubyBzdCkgKGxpc3QgKGZvcm1hdCBuaWwgIn5kTX5kQyAtPiIgbSBjKSkpKQogICAgICAgIChtYWtlLWVzdGFkbyA6bWwgKCsgKGVzdGFkby1tbCBzdCkgbSkgOmNsICgrIChlc3RhZG8tY2wgc3QpIGMpCiAgICAgICAgICAgICAgICAgICAgIDptciAoLSAoZXN0YWRvLW1yIHN0KSBtKSA6Y3IgKC0gKGVzdGFkby1jciBzdCkgYykKICAgICAgICAgICAgICAgICAgICAgOnNpZGUgMAogICAgICAgICAgICAgICAgICAgICA6Y2FtaW5vIChhcHBlbmQgKGVzdGFkby1jYW1pbm8gc3QpIChsaXN0IChmb3JtYXQgbmlsICJ+ZE1+ZEMgPC0iIG0gYykpKSkpKSkKCihkZWZ1biBpZ3VhbGVzIChhIGIpCiAgKGFuZCAoPSAoZXN0YWRvLW1sIGEpIChlc3RhZG8tbWwgYikpICg9IChlc3RhZG8tY2wgYSkgKGVzdGFkby1jbCBiKSkKICAgICAgICg9IChlc3RhZG8tbXIgYSkgKGVzdGFkby1tciBiKSkgKD0gKGVzdGFkby1jciBhKSAoZXN0YWRvLWNyIGIpKQogICAgICAgKD0gKGVzdGFkby1zaWRlIGEpIChlc3RhZG8tc2lkZSBiKSkpKQoKKGRlZnVuIHJlcGV0aWRvLXAgKG51ZXZvIGhpc3RvcmlhbCkKICAoc29tZSAobGFtYmRhIChlKSAoaWd1YWxlcyBlIG51ZXZvKSkgaGlzdG9yaWFsKSkKCihkZWZwYXJhbWV0ZXIgKnZpYWplcyogJygoMiAwKSAoMCAyKSAoMSAxKSAoMSAwKSAoMCAxKSkpCgo7OyBDb250YWRvciBnbG9iYWwgcGFyYSBpZGVudGlmaWNhciBsYXMgc29sdWNpb25lcwooZGVmcGFyYW1ldGVyICpjb250YWRvci1zb2x1Y2lvbmVzKiAwKQoKKGRlZnVuIHJlc29sdmVyIChlc3RhZG8gZmluYWwgaGlzdG9yaWFsKQogICh3aGVuIChpZ3VhbGVzIGVzdGFkbyBmaW5hbCkKICAgIChpbmNmICpjb250YWRvci1zb2x1Y2lvbmVzKikKICAgIChtb3N0cmFyLXNvbHVjaW9uIChyZXZlcnNlIChjb25zIGVzdGFkbyBoaXN0b3JpYWwpKSAqY29udGFkb3Itc29sdWNpb25lcyopCiAgICA7OyBOTyBwb25lbW9zIHJldHVybi1mcm9tIHBhcmEgcXVlIHNpZ2EgYnVzY2FuZG8gbcOhcyBjYW1pbm9zCiAgICAocmV0dXJuLWZyb20gcmVzb2x2ZXIgbmlsKSkgCgogIChkb2xpc3QgKHYgKnZpYWplcyopCiAgICAobGV0KiAoKG0gKGZpcnN0IHYpKQogICAgICAgICAgIChjIChzZWNvbmQgdikpCiAgICAgICAgICAgKG51ZXZvIChtb3ZlciBlc3RhZG8gbSBjKSkpCiAgICAgICh3aGVuIChhbmQgKGVzdGFkby12YWxpZG8tcCBudWV2bykKICAgICAgICAgICAgICAgICAobm90IChyZXBldGlkby1wIG51ZXZvIGhpc3RvcmlhbCkpKQogICAgICAgIChyZXNvbHZlciBudWV2byBmaW5hbCAoY29ucyBlc3RhZG8gaGlzdG9yaWFsKSkpKSkpCgooZGVmdW4gcGVyc29uYXMgKG0gYykKICAoY29uY2F0ZW5hdGUgJ3N0cmluZwogICAgICAgICAgICAgICAobWFrZS1zdHJpbmcgbSA6aW5pdGlhbC1lbGVtZW50ICNcTSkKICAgICAgICAgICAgICAgKG1ha2Utc3RyaW5nIGMgOmluaXRpYWwtZWxlbWVudCAjXEMpKSkKCihkZWZ1biBsYWRvLWEtc3RyaW5nIChtIGMpCiAgKGZvcm1hdCBuaWwgIlt+M2FdIiAocGVyc29uYXMgbSBjKSkpCgooZGVmdW4gbW9zdHJhci1wYXNvIChhbnRlcmlvciBhY3R1YWwpCiAgKGxldCAoKHNpZGUgKGVzdGFkby1zaWRlIGFudGVyaW9yKSkKICAgICAgICAobW92aW1pZW50byAoY2FyIChsYXN0IChlc3RhZG8tY2FtaW5vIGFjdHVhbCkpKSkpCiAgICAoZm9ybWF0IHQgIn4lfmEgfmEgfmEgIHwgQWNjacOzbjogfmEiIAogICAgICAgICAgICAobGFkby1hLXN0cmluZyAoZXN0YWRvLW1sIGFudGVyaW9yKSAoZXN0YWRvLWNsIGFudGVyaW9yKSkKICAgICAgICAgICAgKGlmICg9IHNpZGUgMCkgIiBCIH5+fn4gICAiICIgICB+fn5+IEIgIikKICAgICAgICAgICAgKGxhZG8tYS1zdHJpbmcgKGVzdGFkby1tciBhbnRlcmlvcikgKGVzdGFkby1jciBhbnRlcmlvcikpCiAgICAgICAgICAgIG1vdmltaWVudG8pKSkKCihkZWZ1biBtb3N0cmFyLXNvbHVjaW9uIChjYW1pbm8gbikKICAoZm9ybWF0IHQgIn4lfiU9PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT0iKQogIChmb3JtYXQgdCAifiVTT0xVQ0nDk04gTsOaTUVSTyB+ZCIgbikKICAoZm9ybWF0IHQgIn4lPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09IikKICAobG9vcCBmb3IgKGEgYikgb24gY2FtaW5vIHdoaWxlIGIgZG8gKG1vc3RyYXItcGFzbyBhIGIpKQogIChsZXQgKCh1IChjYXIgKGxhc3QgY2FtaW5vKSkpKQogICAgKGZvcm1hdCB0ICJ+JX5hICAgIH5+fn4gQiAgfmEgIHwgwqFMbGVnYXJvbiEiIAogICAgICAgICAgICAobGFkby1hLXN0cmluZyAoZXN0YWRvLW1sIHUpIChlc3RhZG8tY2wgdSkpCiAgICAgICAgICAgIChsYWRvLWEtc3RyaW5nIChlc3RhZG8tbXIgdSkgKGVzdGFkby1jciB1KSkpKSkKCihkZWZ1biBtYWluICgpCiAgKHNldGYgKmNvbnRhZG9yLXNvbHVjaW9uZXMqIDApIDsgUmVpbmljaWFyIGNvbnRhZG9yCiAgKGxldCAoKGluaWNpbyAobWFrZS1lc3RhZG8gOm1sIDMgOmNsIDMgOm1yIDAgOmNyIDAgOnNpZGUgMCA6Y2FtaW5vICcoKSkpCiAgICAgICAgKGZpbiAobWFrZS1lc3RhZG8gOm1sIDAgOmNsIDAgOm1yIDMgOmNyIDMgOnNpZGUgMSA6Y2FtaW5vICcoKSkpKQogICAgKHJlc29sdmVyIGluaWNpbyBmaW4gJygpKQogICAgKGZvcm1hdCB0ICJ+JX4lQsO6c3F1ZWRhIGZpbmFsaXphZGEuIFNlIGVuY29udHJhcm9uIH5kIHNvbHVjaW9uZXMufiUiICpjb250YWRvci1zb2x1Y2lvbmVzKikpKQoKKG1haW4p