(defun depth-first-search (start goal been-list moves)
  (cond ((equal start goal)
         (reverse (cons start been-list)))
        (t (try-moves start goal been-list moves moves))))

; Try-moves scans down the list of moves in moves-to-try,
; attempting to generate a child state.  If it produces
; this state, it calls depth-first-search to complete the search.

(defun try-moves (start goal been-list moves-to-try moves)
  (cond ((null moves-to-try) nil)
        ((member start been-list :test #'equal) nil)
        (t (let ((child (funcall (car moves-to-try) start)))
             (if child
               (or (depth-first-search (funcall (car moves-to-try) start)
                                       goal
                                       (cons start been-list)
                                       moves)
                   (try-moves start goal been-list (cdr moves-to-try) moves))
               (try-moves start goal been-list (cdr moves-to-try) moves))))))

(defun valid-move (a b)
    (if (and (> a 0) (< a 4) (> b 0) (< b 4)) T nil)
)


(defun moves (state)
    (cond
        ((valid-move (+ (car state) 1) (+ (car (cdr state)) 2)) (append (list (+ (car state) 1)) (list (+ (car (cdr state)) 2))))
        ((valid-move (+ (car state) 2) (+ (car (cdr state)) 1)) (append (list (+ (car state) 2)) (list (+ (car (cdr state)) 1))))
        ((valid-move (+ (car state) 1) (- (car (cdr state)) 2)) (append (list (+ (car state) 1)) (list (- (car (cdr state)) 2))))
        ((valid-move (- (car state) 2) (+ (car (cdr state)) 1)) (append (list (- (car state) 2)) (list (+ (car (cdr state)) 1))))
        )
)
(defun path (state goal been-list)
   (cond
    ((null state) nil)
    ((equal state goal) (reverse (cons state been-list)))
    ((not (member state been-list :test #'equal))
     (or
      (path (moves state) goal (cons state been-list))
      )))
)

(defun solve (state goal)
    (path state goal nil)
)

(defun run-depth (start goal moves)
  (depth-first-search start goal () moves))

; dodajte ja listata na potezi koi treba da se probaat za sekoja sostojba i odkomentirajte ja slednata linija
(run-depth '(1 1) '(3 3)  '(moves))
(print (solve '(1 1) '(3 3)))