;Solution to Water Jug Problem using Depth First Search
;By: Rohit Kumar
;Dt: 12/10/02

(setq global-list ())
(setq flag nil)
(setq solved nil)

(defun CheckRepeat (x)
	(setq CheckRepeat nil)
	(let (temp)
		(setq flag nil)
		(dolist (temp global-list)
			(if (equal x temp)
				(setq flag t)
			)
			(if flag (return-from CheckRepeat))
		)
	)
)

(defun DFS (x y)
	(CheckRepeat (cons x (cons y ())))
	(if flag (return-from DFS))
	(setq global-list (cons (cons x (cons y ())) global-list))
	(if (eq 2 x) (setq solved t))
	(if solved (return-from DFS))
	(if (< x 4)
		(DFS 4 y)
		(if solved (return-from DFS))
	)
	(if (< y 4)
		(DFS x 3)
		(if solved (return-from DFS))
	)
	(if (> x 0) 
		(DFS 0 y)
		(if solved (return-from DFS))
	)
	(if (> y 0) 
		(DFS x 0)
		(if solved (return-from DFS))
	)
	(if (and (<= (+ x y) 4) (> y 0))
		(DFS (+ x y) 0)
		(if solved (return-from DFS))
	)
	(if (and (<= (+ x y) 3) (> x 0))
		(DFS 0 (+ x y))
		(if solved (return-from DFS))
	)
	(if (and (>= (+ x y) 4) (> y 0))
		(DFS 4 (- y (- 4 x)))
		(if solved (return-from DFS))
	)
	(if (and (>= (+ x y) 3) (> x 0))
		(DFS (- x (- 3 y)) 3)
		(if solved (return-from DFS))
	)
	(if (and (eq 0 x) (eq 2 y))
		(DFS 2 0)
		(if solved (return-from DFS))
	)
	(if (eq 2 x)
		(DFS 0 y)
		(if solved (return-from DFS))
	)
	(setq global-list (cdr global-list))
)

(defun SolveWaterJug ()
	(setq global-list ())
	(setq solved nil)
	(DFS 0 0)
	(dolist (onestep (reverse global-list))
		(print onestep)
	)
)