;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; This file contains several test cases and a few support routines to
; help you test your heuristics.
;
; The functions in this file depend on YOUR sbp-children function, and
; you must also use your own heuristic.
;
; There are several different types of tests using a few different puzzles:
;   - the eight puzzle
;   - the fifteen puzzle
;   - some other puzzle geometries
;
; If you don't want the message printed every 100 nodes, do the following:
;
;    (define astar-debug #f)
;
; Set it to #t to turn it back on again.
; 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; This procedure is used to actually run the astar algorithm with your
; heuristic and needs your sbp-children procedure.
;
(define (run-heuristic start goal heuristic)
  (display "; ****************************************")
  (newline)
  (display "; START STATE: ")
  (display start)
  (newline)
  (display "; GOAL STATE: ")
  (display goal)
  (newline)
  (display ";")
  (newline)
  (astar start goal sbp-children heuristic))

; the 0 heuristic
(define (zero-heuristic state goal)
  0)

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Eight puzzle examples
;
; Please note that the number of states evaluated I've listed below
; may not exactly match your implementation.  (Why is this so?  This
; would be a good quiz question, don't you think?)  
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


; This is an easy one --- optimal solution is 8 moves; the zero
; heuristic finds this after evaluating 297 states.  The manhattan
; heuristic only evaluates 16 states!
; 
(define	(ep-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 --- 10 moves; manhattan = 26 states (42 in DrScheme)
;
(define (ep-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)))

; Yet another easy one --- 14 moves, zero heuristic = 5342 states,
; manhattan = 40 states (64 in DrScheme)
;
(define (ep-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 --- 20 moves, manhattan = 469 states
; (1954 in DrScheme)
;
(define (ep-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 --- 24 moves; the manhattan
; heuristic evaluates almost 2500 states (10279 in DrScheme)
; 
(define (ep-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 (ep-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).  However, it not always
; possible to get from one random state to another...
;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; the fifteen puzzle
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; easy --- 22 moves, manhattan = 120 states (297 in DrScheme)
; 
(define (fp-test1 heuristic)
  (let ((ss '((6 5 2 3) (1 14 8 4) (9 13 7 11) (10 15 12 space)))
	(gs '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 space))))
    (run-heuristic ss gs heuristic)))

; hard...
; 
(define (fp-test2 heuristic)
  (let ((ss '((1 5 9 15) (2 6 10 13) (3 7 11 14) (4 8 12 space)))
	(gs '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 space))))
    (run-heuristic ss gs heuristic)))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; other geometries
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; 21 moves, manhattan evaluated 296 states
; 
(define (try-me heuristic)
  (let ((ss '(("T" "R" "Y") ("M" "E" space)))
	(gs '(("M" "E" space) ("T" "R" "Y"))))
    (run-heuristic ss gs heuristic)))