; eight.l
; Michael Schuld, Nick Combs
; Solution to Program 3
; CS 436 - Artifical Intelligence

; lookup table for the places that b can swap to when at position b
(defvar *table* (list
    (list 1 3)          ; b = 0
    (list 0 2 4)        ; b = 1
    (list 1 5)          ; b = 2
    (list 0 4 6)        ; b = 3
    (list 1 3 5 7)      ; b = 4
    (list 2 4 8)        ; b = 5
    (list 3 7)          ; b = 6
    (list 4 6 8)        ; b = 7
    (list 5 7)          ; b = 8
))

; solve: the main function to be called by the test program
; 
; parameters:
;   start - the start state of the board
;   goal - the state we are searching for in the tree
;
; output - the output is simply the depth that the solution was found at
;
(defun solve (start goal)
    (let
        (
            (b (position 'b start))
        )

        (do
            ( (max 0 (+ max 1)) )
            ( (check-children start b goal 0 max) max)
        )
    )
)

; check-children: a recursive depth first search of the children
;
; parameters:
;   state - the current state of the board
;   b - the position of the blank in the board
;   goal - the state we need to get to (solution)
;   depth - the current depth of the search
;   max - the depth limit of the search
;
; output:
;   the result will be returned as the found solution (if found) or nil
;
(defun check-children (state b goal depth max)
    (cond
        ((equal state goal) depth)
        ((= depth max) nil)
        (t
            (dolist (swap (nth b *table*))
                (let*
                    (
                        ; set the child state to be the swapped state with the next swap location
                        (child (swap-b state swap b))      

                        ; set the result to a recursive call to check-children and increment our depth counter                        
                        (result (check-children child swap goal (+ 1 depth) max))
                    )

                    (if result (return-from check-children result))
                )
            )
        )
    )
)

; swap-b: a function to swap element a with 'b in the state
;
; parameters:
;   state - the list to manipulate
;   a - the index to swap b with
;   b - the index of the current 'b
;
; output: a copy of the original list with a and 'b items swapped
;
(defun swap-b (state a b)
    (let
        ( (copy (copy-list state)) )                    ; the copy to return
        (rotatef (nth a copy) (nth b copy))             ; swap the two elements using rotatef
        (return-from swap-b copy)                       ; return the copy out of the swap-b
    )
)