;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; CSCI--4150 Introduction to Artificial Intelligence
; Sliding Block Puzzles, Version 1.1.1
; Copyright (C) 2002 Wesley H. Huang.  All rights reserved.
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Some 8-puzzle and 15-puzzle problems with complete goal states.
; Your Manhattan-distance heursistic should work well for these
; problems.
;
; Note that the number of states I report for solving a puzzle may not
; be the same for you, even though we might run the exact same
; heuristic.  (Why is this?)
; 
; 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...
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; An easy one...
; 
(define ep1-start '((empty A B) (C D E) (F G H)))
(define ep1-goal '((empty D B) (A E H) (C F G)))
(define (ep1-goal? s)
  (sbp-compare s ep1-goal))
(define (ep1) ; a handy function to run this puzzle with your heuristic
  (solve ep1-start ep1-goal? (lambda (s)
			       (manhattan-dist s ep1-goal))))

; Another easy one
;
(define ep2-start '((A F B) (G D C) (E H empty)))
(define ep2-goal '((A B C) (D E F) (G H empty)))
(define (ep2-goal? s)
  (sbp-compare s ep2-goal))
(define (ep2) ; a handy function to run this puzzle with your heuristic
  (solve ep2-start ep2-goal? (lambda (s)
			       (manhattan-dist s ep2-goal))))

; Yet another easy one
;
(define ep3-start '((H C E) (B A F) (D G empty)))
(define ep3-goal '((A B C) (D E F) (G H empty)))
(define (ep3-goal? s)
  (sbp-compare s ep3-goal))
(define (ep3) ; a handy function to run this puzzle with your heuristic
  (solve ep3-start ep3-goal? (lambda (s)
			       (manhattan-dist s ep3-goal))))

; A more difficult one
;
(define ep4-start '((H E A) (G D C) (B F empty)))
(define ep4-goal '((A B C) (D E F) (G H empty)))
(define (ep4-goal? s)
  (sbp-compare s ep4-goal))
(define (ep4) ; a handy function to run this puzzle with your heuristic
  (solve ep4-start ep4-goal? (lambda (s)
			       (manhattan-dist s ep4-goal))))

; Moderately difficult
; 
(define ep5-start '((C B G) (E D H) (A F empty)))
(define ep5-goal '((A B C) (D E F) (G H empty)))
(define (ep5-goal? s)
  (sbp-compare s ep5-goal))
(define (ep5) ; a handy function to run this puzzle with your heuristic
  (solve ep5-start ep5-goal? (lambda (s)
			       (manhattan-dist s ep5-goal))))
(define (ep5^2)	
  (solve ep5-start ep5-goal? (lambda (s)
			       (square (manhattan-dist s ep5-goal)))))

; Tough (?)
;
(define ep6-start '((H G F) (E D C) (B A empty)))
(define ep6-goal '((A B C) (D E F) (G H empty)))
(define (ep6-goal? s)
  (sbp-compare s ep6-goal))
(define (ep6) ; a handy function to run this puzzle with your heuristic
  (solve ep6-start ep6-goal? (lambda (s)
			       (manhattan-dist s ep6-goal))))
(define (ep6^2)	
  (solve ep6-start ep6-goal? (lambda (s)
			       (square (manhattan-dist s ep6-goal)))))
	

;;;;;;;;;;;;;;;;
; fifteen puzzle problems
;;;;;;;;;;;;;;;;

; easy
; 
(define fp1-start '((F E B C) (A P H D) (J N G L) (K Q M empty)))
(define fp1-goal '((A B C D) (E F G H) (J K L M) (N P Q empty)))
(define (fp1-goal? s)
  (sbp-compare s fp1-goal))
(define (fp1) ; a handy function to run this puzzle with your heuristic
  (solve fp1-start fp1-goal? (lambda (s)
			       (manhattan-dist s fp1-goal))))

; hard...
; 
(define fp2-start '((A E J Q) (B F K N) (C G L P) (D H M empty)))
(define fp2-goal '((A B C D) (E F G H) (J K L M) (N P Q empty)))
(define (fp2-goal? s)
  (sbp-compare s fp2-goal))
(define (fp2) ; a handy function to run this puzzle with your heuristic
  (solve fp2-start fp2-goal? (lambda (s)
			       (manhattan-dist s fp2-goal))))
(define (fp2^2)	
  (solve fp2-start fp2-goal? (lambda (s)
			       (square (manhattan-dist s fp2-goal)))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Some unit-block puzzles of different geometries
; 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define try-me-start '((t r y)
		       (m e empty)))
(define try-me-goal '((m e empty)
		      (t r y)))
(define (try-me-goal? s)
  (sbp-compare s try-me-goal))
(define (try-me)
  (solve try-me-start try-me-goal? (lambda (s)
				     (manhattan-dist s try-me-goal))))


(define now-try-me-start '((n o w)
			   (t r y)
			   (m e empty)))
(define now-try-me-goal '((m e empty)
			  (o w n)
			  (t r y)))
(define (now-try-me-goal? s)
  (sbp-compare s now-try-me-goal))
(define (now-try-me)
  (solve now-try-me-start
	 now-try-me-goal? 
	 (lambda (s)
	   (manhattan-dist s now-try-me-goal))))



; Sam Loyd's moving day puzzle
; goal is to exchange blocks P and Q
;
(define moving-day-start '((A empty P)
			   (B   C   Q)))
(define moving-day-goal '((#f #f Q)
			  (#f #f P)))
(define (moving-day-goal? s)
  (sbp-compare s moving-day-goal))
(define (moving-day)
  (solve moving-day-start
	 moving-day-goal?
	 (lambda (s)
	   (manhattan-dist s moving-day-goal))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Hughes puzzle
; 
; Goal is to move block Q to the lower right corner.  Can be solved in
; 31 moves.  (Some people would say that this can be done in 21 moves
; --- except that their "moves" are allowed to move a block more than
; 1 square which our implementation does not do.)
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define hughes-start '(( Q  empty  A)
		       ((Q) empty  B)
		       ( C    D   (D))
		       ( E   (E)   F)))
(define hughes-goal '((#f #f #f)
		      (#f #f #f)
		      (#f #f Q)
		      (#f #f (Q))))
(define (hughes-goal? s)
  (sbp-compare s hughes-goal))
(define (hughes)
  (solve hughes-start hughes-goal? (lambda (s)
				     (manhattan-dist s hughes-goal))))
(define (hughes^2)
  (solve hughes-start hughes-goal? (lambda (s)
				     (square (manhattan-dist s hughes-goal)))))
(define (my-hughes)
  (solve hughes-start hughes-goal? (lambda (s)
				     (sbp-heuristic s hughes-goal))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define w1-start '((q (q) empty e)
		   ((q) (q) (e) (e))
		   (empty f (f) empty)
		   (a empty d b)
		   ((a) empty empty (b))))
(define (w1)
  (solve w1-start w-goal? (lambda (s) 
			    (manhattan-dist s w-goal))))
(define (w1^2)
  (solve w1-start w-goal? (lambda (s) 
			    (square (manhattan-dist s w-goal)))))
(define (my-w1)
  (solve w1-start w-goal? (lambda (s) 
			    (sbp-heuristic s w-goal))))

(define w2-start '((a g (g) h)
		   ((a) q (q) f)
		   (empty (q) (q) (f))
		   (empty empty empty e)
		   (b d (e) (e))))
(define (w2)
  (solve w2-start w-goal? (lambda (s) 
			    (manhattan-dist s w-goal))))
(define (w2^2)
  (solve w2-start w-goal? (lambda (s) 
			    (square (manhattan-dist s w-goal)))))
(define (my-w2)
  (solve w2-start w-goal? (lambda (s) 
			    (sbp-heuristic s w-goal))))

(define w3-start '((empty q (q) a)
		   (empty (q) (q) (a))
		   (empty empty empty h)
		   (d g (g) e)
		   (b f (e) (e))))
(define (w3)
  (solve w3-start w-goal? (lambda (s) 
			    (manhattan-dist s w-goal))))
(define (w3^2)
  (solve w3-start w-goal? (lambda (s) 
			    (square (manhattan-dist s w-goal)))))
(define (my-w3)
  (solve w3-start w-goal? (lambda (s) 
			    (sbp-heuristic s w-goal))))

 

(define w-goal '((#f #f #f #f)
		 (#f #f #f #f)
		 (#f #f #f #f)
		 (#f q (q) #f)
		 (#f (q) (q) #f)))
(define (w-goal? s)
  (sbp-compare s w-goal))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Ma's puzzle
; 
; Goal is to move blocks P and Q to form a rectangle in the upper
; right corner.  Can be solved in 23 moves?
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define mas-start '((  A    (A)  (A)  Q    (Q))
		    (  B    (B)   C  (C)   (Q))
		    (  P     D   (D)  E    (E))
		    ( (P)   (P)   F  (F)   (F))
		    (empty empty  G empty empty)))
(define mas-goal '((#f #f  #f  q (q))
		   (#f #f #f p (q))
		   (#f #f #f (p) (p))
		   (#f #f #f #f #f)
		   (#f #f #f #f #f)))
(define (mas-goal? s)
  (sbp-compare s mas-goal))

; you won't solve the puzzle with the manhattan heuristic, but here they are
(define (mas)
  (solve mas-start mas-goal? (lambda (s)
 			       (manhattan-dist s mas-goal))))
(define (mas^2)
  (solve mas-start mas-goal? (lambda (s)
 			       (square (manhattan-dist s mas-goal)))))
(define (my-mas)
  (solve mas-start mas-goal? (lambda (s)
 			       (sbp-heuristic s mas-goal))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; the "ten block" puzzle
; 
; Goal is to exchange blocks P and Q.  Can be done in 47 moves?
; 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define ten-block-start '((  p    (p)   a   b)
			  ( (p)   (p)   c  (c))
			  (empty empty  d   e)
			  (  q    (q)   f  (f))
			  ( (q)   (q)   g   h)))

(define ten-block-goal '((  q    (q)  #f  #f)
			 ( (q)   (q)  #f  #f)
			 ( #f    #f   #f  #f)
			 (  p    (p)  #f  #f)
			 ( (p)   (p)  #f  #f)))
(define (ten-block-goal? s)
  (sbp-compare s ten-block-goal))

; you probably won't solve it with these heuristics, but here they are
(define (ten-block)
  (solve ten-block-start
	 ten-block-goal?
	 (lambda (s)
	   (manhattan-dist s ten-block-goal))))
(define (ten-block^2)
  (solve ten-block-start
	 ten-block-goal?
	 (lambda (s)
	   (square (manhattan-dist s ten-block-goal)))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; The goal for all these puzzles is to move the E block (the only 2x2
; block) to the middle of the right side of the puzzle.  Therefore,
; they all have the same goal predicate "p-goal?"
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


(define p1-start '((a (a) b c d)
		   (e (e) f g empty)
		   ((e) (e) h j empty)
		   (k (k) l m n)))
; I don't think you'll solve the puzzle with these, but here they are
(define (p1)
  (solve p1-start p-goal? (lambda (s)
			    (manhattan-dist s p-goal))))
(define (p1^2)
  (solve p1-start p-goal? (lambda (s)
			    (square (manhattan-dist s p-goal)))))

(define p2-start '((a (a) b c d)
		   (e (e) f g empty)
		   ((e) (e) h j empty)
		   (k (k) l (l) m)))
(define p3-start '((a (a) b c d)
		   (e (e) f g empty)
		   ((e) (e) (f) h empty)
		   (j (j) k l m)))
(define p4-start '((a (a) b (b) c)
		   (e (e) d f empty)
		   ((e) (e) (d) g empty)
		   (h (h) j (j) k)))
(define p5-start '((a (a) b c d)
		   (e (e) f g empty)
		   ((e) (e) (f) h empty)
		   (j (j) k (k) l)))
(define p6-start '((a (a) b (b) c)
		   (e (e) f g empty)
		   ((e) (e) (f) h empty)
		   (d (d) j (j) k)))

(define p-goal '((#f #f #f #f #f)
		 (#f #f #f e (e))
		 (#f #f #f (e) (e))
		 (#f #f #f #f #f)))
(define (p-goal? s)
  (sbp-compare s p-goal))
		   


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; John Conway's Century puzzle (can be done in 100 moves)
; 
; Note: the 1x2 block (E) under the 2x2 block (Q) was drawn in the
; middle (between two rows).  I had to move it to one side, so I don't
; know whether this counts as a move or not.
;
; Goal is to move (here) block Q to the middle of the bottom two rows.
; 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define century-start '(( A   Q   (Q)   B)
			( C  (Q)  (Q)   D)
			((C)  E  empty (D))
			( F  (E) empty  F)
			( G  (G)   H   (H))))
(define century-goal '((#f #f  #f  #f)
		       (#f #f  #f  #f)
		       (#f #f  #f  #f)
		       (#f  Q  (Q) #f)
		       (#f (Q) (Q) #f)))
(define (century-goal? s)
  (sbp-compare s century-goal))

; you probably won't solve the problem with these heuristics but here they are
(define (century)
  (solve century-start
	 century-goal?
	 (lambda (s)
	   (manhattan-dist s century-goal))))
(define (century^2)
  (solve century-start
	 century-goal?
	 (lambda (s)
	   (square (manhattan-dist s century-goal)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; "Piano moving" puzzles
; 
; found at http://www.doc.ic.ac.uk/~rb/group-projects/piano/
;
; Goal is to exchange the four unit blocks (here W, X, Y, and Z) with
; the 2x2 block Q.  (It does not matter what the arrangement of W--Z
; is in the goal.)
;
; Note that the goal for these puzzles is written in a different
; template format from the previous puzzles.  Here, when we care what
; block is in a cell, give a list of all allowable blocks.  This kind
; of template can be given to the "sbp-compare2" procedure.
;
(define piano-moving-1-start '((  A   W X     B)
			       ( (A)  Y Z    (B))
			       (empty C (C) empty)
			       (  D   Q (Q)   E)
			       ( (D) (Q) (Q) (E))))
(define piano-moving-1-goal '((#f    (Q)      ((Q))   #f)
			      (#f   ((Q))     ((Q))   #f)
			      (#f    #f        #f     #f)
			      (#f (W X Y Z) (W X Y Z) #f)
			      (#f (W X Y Z) (W X Y Z) #f)))
(define (piano-moving-1-goal? s)
  (sbp-compare2 s piano-moving-1-goal))
			      

(define piano-moving-2-start '((  A   W X     B)
			       ( (A)  Y Z    (B))
			       (empty C (C) empty)
			       (  d   e (e)   f)
			       ( (d) (e)(e)  (f))
			       (  g  (g) h   (h))
			       (  j   Q (Q)   k)
			       ( (j) (Q) (Q) (k))))
(define piano-moving-2-goal '((#f    (Q)      ((Q))   #f)
			      (#f   ((Q))     ((Q))   #f)
			      (#f    #f        #f     #f)
			      (#f    #f        #f     #f)
			      (#f    #f        #f     #f)
			      (#f    #f        #f     #f)
			      (#f (W X Y Z) (W X Y Z) #f)
			      (#f (W X Y Z) (W X Y Z) #f)))
(define (piano-moving-2-goal? s)
  (sbp-compare2 s piano-moving-2-goal))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; example states from Assignment 2
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define example-a '((  A    (A)    B      C     D)
		    ( (A)   (A)   (B)     E   empty)
		    (  F    (F)  empty    G    (G))
		    (empty   H    (H)   empty   J)))
(define example-b '((C B H (H) D)
		    (empty (B) empty E empty)
		    (F (F) A (A) empty)
		    (G (G) (A) (A) J)))
(define example-c '((A (A) (A) (A) empty empty empty )
		    (B (B) empty C (C) (C) (E) )
		    (empty (B) D (C) (C) (C) (E) )
		    (empty (B) empty empty E (E) (E))
		    (empty F (F) empty (E) (E) (E))))
(define example-d '((empty a empty b)
		    (c (c) (c) (b))
		    ((c) d e (e))
		    (empty (d) (e) (e))
		    (empty  (d) (d) empty)
		    (empty  (d) (d) empty)
		    (f (f) empty empty )))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; utility procedures
(define (square x)
  (* x x))