;;   This is the definition of a function that determines the legal
;;   moves in the 8-puzzle given the state of the board. The
;;   function "moves" (THE ONLY ONE YOU SHOULD USE) takes a
;;   state representation and return a list of one or more
;;   moves with the corresponding final states 
;;   For instance, the following board
;;
;;     +---+---+---+
;;     | 2 | e | 3 |
;;     +---+---+---+
;;     | 4 | 7 | 8 |
;;     +---+---+---+
;;     | 1 | 5 | 6 |
;;     +---+---+---+
;;
;;   allows the empty tile to be moved down, to the left
;;   and to the right. Accordingly:
;;
;;   USER(10): (moves '(2 e 3 4 7 8 1 5 6))
;;   ( (D (2 7 3 4 E 8 1 5 6))
;;     (L (E 2 3 4 7 8 1 5 6))
;;     (R (2 3 E 4 7 8 1 5 6))
;;    )
;;
;;   (the string format is mine: just to make it clear. What
;;   you actually get on your terminal is one big line)

(defun epos (l)
  (if (equal 'e (first l)) 1
    (+ 1 (epos (rest l)))
   )
)



(defun movelft (l pos)
  (append (butlast l (- (length l) (- pos 2)))
   '(e)
   (cons (first (nthcdr (- pos 2) l))
   (nthcdr pos l)
  )
 )
)

(defun movergt (l pos)
  (append (butlast l (- (length l) (- pos 1)))
    (cons (first (nthcdr pos l))
    '(e)
   )
   (nthcdr (+ pos 1) l)
  )
 )
 

(defun moveup (l pos)
  (append (butlast l (- (length l) (- pos 4)))
   '(e)
   (butlast (nthcdr (- pos 3) l) (- (length l) (- pos 1)))
   (cons (first (nthcdr (- pos 4) l))
   (nthcdr pos l)
  )
 )
)

(defun movedwn (l pos)
  (append (butlast l (- (length l) (- pos 1)))
   (cons (first (nthcdr (+ pos 2) l)) 
 (butlast (nthcdr pos l) (- (length l) (+ pos 2))))
   '(e)
   (nthcdr (+ pos 3) l)
 )
)

(defun up (s p) (when (> p 3) (list 'u (moveup s p))))

(defun dwn (s p) (when (< p 7) (list 'd (movedwn s p))))

(defun lft (s p)
  (when (> (mod (- p 1) 3) 0) (list 'l (movelft s p))))

(defun rgt (s p)
  (when (> (mod p 3) 0) (list 'r (movergt s p))))

(defun directions (s p)
  (remove-if
   #'(lambda (q) (null q))
   (list (up s p) (dwn s p) (lft s p) (rgt s p)))
  )

(defun moves (s)
  (directions s (epos s)))