;;; -*- mode: lisp; syntax: common-lisp -*-

(defvar *square-side*)

(let ((movements '((l . (-1 0)) (r . (1 0)) (u . (0 -1)) (d . (0 1)))))
  (defun move (state dir)
    (let* ((p (position 0 state))
           (x (mod p *square-side*))
           (y (floor p *square-side*)))
      (unless (or (and (= x 0) (eq dir 'l))
                  (and (= x 2) (eq dir 'r))
                  (and (= y 0) (eq dir 'u))
                  (and (= y 2) (eq dir 'd)))
        (let* ((d (cdr (assoc dir movements)))
               (new-x (+ x (first d)))
               (new-y (+ y (second d)))
               (new-pos (+ (* new-y *square-side*) new-x))
               (result (copy-list state)))
          (rotatef (elt result p) (elt result new-pos))
          result)))))

(defun find-solution (initial goal limit)
  (let ((volt (make-hash-table :test 'equal))
        (*square-side* (isqrt (length goal)))
        result)
    (labels ((rec (state &optional acc (level 0))
               (cond ((equal state goal)
                      (setf result acc))
                     ((> level limit) nil)
                     (t (dolist (direction '(l r d u))
                          (let ((new-state (move state direction)))
                            (when (and new-state)
                              (let ((old (gethash new-state volt)))
                                (when (or (null old) (> old level))
                                  (setf (gethash new-state volt) level)
                                  (rec new-state (cons direction acc)
                                       (1+ level)))))))))))
      (setf (gethash initial volt) 0)
      (rec initial)
      (nreverse result))))

(find-solution '(3 5 7 8 0 2 4 6 1) '(0 1 2 3 4 5 6 7 8) 20)

;;; (L D R U R U L D R D L U R U L D L U)