;
; This file contains several test cases and a few support routines to
; help you test out your heuristics
;
; To use the test functions, you must give them a heuristic function.
; For example:
;
;   (test1 ep-zero-heuristic)      or     (test1 ep-manhattan)
;
; See individual test procedures below for some comments.
;
; While testing, you probably want to set the "astar-debug" variable to
; #t so that you get a message every 100 nodes.  (I just changed the default 
; in the code.
;
;  --wh   
;

(define run-heuristic
  (lambda (ss gs h)
      (display "; ****************************************\n")
      (display "; STATE STATE: ")
      (display ss)
      (display "\n; GOAL STATE:  ")
      (display gs)
      (display "\n")
      (astar ss gs ep-children h)))

(define (ep-zero-heuristic current goal)
  0)



;
; This is an easy one --- the zero heuristic finds this after evaluating
; 297 states.  The manhattan heuristic only evaluates 16 states!
; 
(define	(test1 heuristic)
  (let ((ss '(space 1 2 3 4 5 6 7 8))      ; start state
	(gs '(space 4 2 1 5 8 3 6 7)))     ; goal state
    (run-heuristic ss gs heuristic)))

;
; another easy one --- zero heuristic = 806 states, manhattan = 25 states
;
(define (test2 heuristic)
  (let ((ss '(1 6 2 7 4 3 5 8 space))
	(gs '(1 2 3 4 5 6 7 8 space)))
    (run-heuristic ss gs heuristic)))

;
; Here's another easy one --- the zero heuristic evaluates 5342 states, the
; manhattan heuristic 52 states.
;
(define (test3 heuristic)
  (let ((ss '(8 3 5 2 1 6 4 7 space))
	(gs '(1 2 3 4 5 6 7 8 space)))
    (run-heuristic ss gs heuristic)))

;
; Here's a more difficult one --- manhattan evaluates 607 states, 
; the zero-heuristic evaluates a lot of states...  (i didn't wait!)
;
(define (test4 heuristic)
  (let ((ss  '(8 5 1 7 4 3 2 6 space))
	(gs '(1 2 3 4 5 6 7 8 space)))
    (run-heuristic ss gs heuristic)))

;
; This starts to be moderately difficult --- the manhattan heuristic 
; evaluates almost 2900 nodes
; 
(define (test5 heuristic)
  (let ((ss '(3 2 7 5 4 8 1 6 space))
	(gs '(1 2 3 4 5 6 7 8 space)))
    (run-heuristic ss gs heuristic)))

;
; a tough one!
;
(define (test6 heuristic)
  (let ((ss '(8 7 6 5 4 3 2 1 space))
	(gs '(1 2 3 4 5 6 7 8 space)))
    (run-heuristic ss gs heuristic)))
	
;
; By the way, it's easy to make up these test cases --- just take an
; 8 puzzle, start at the goal configuration, and start moving pieces around.  
; The fewer moves you make, the easier it will be.
;
; You can also generate random states with the MIT Scheme "random" function.
; (And some list manipulation...)  See the MIT Scheme reference manual for
; details on the random function.
;