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

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; example states from Assignment 2
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define example-1 '((A 	 A   empty   B 	 C)
		    (A 	 A   empty   B 	 D)
		    (E 	 F     F   empty G)
		    (E empty   G     G   G)))
(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 procedure
(define (square x)
  (* x x))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; 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 "random" procedure (and
; some list manipulation).  However, for any two states, there is not
; always a solution to go from one to the other...  
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

; 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))))

; A more difficult one
; 
(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)))))
(define (c-fp2)	
  (solve fp2-start fp2-goal? (lambda (s)
			       (c-heuristic s fp2-goal))))
(define (i-fp2)	
  (solve fp2-start fp2-goal? (lambda (s)
			       (i-heuristic 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 (c-hughes)
  (solve hughes-start hughes-goal? (lambda (s)
				     (c-heuristic s hughes-goal))))
(define (i-hughes)
  (solve hughes-start hughes-goal? (lambda (s)
				     (i-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 (c-w1)
  (solve w1-start w-goal? (lambda (s) 
			    (c-heuristic s w-goal))))
(define (i-w1)
  (solve w1-start w-goal? (lambda (s) 
			    (i-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 (c-w2)
  (solve w2-start w-goal? (lambda (s) 
			    (c-heuristic s w-goal))))
(define (i-w2)
  (solve w2-start w-goal? (lambda (s) 
			    (i-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 (c-w3)
  (solve w3-start w-goal? (lambda (s) 
			    (c-heuristic s w-goal))))
(define (i-w3)
  (solve w3-start w-goal? (lambda (s) 
			    (i-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 (c-mas)
  (solve mas-start mas-goal? (lambda (s)
 			       (c-heuristic s mas-goal))))
(define (i-mas)
  (solve mas-start mas-goal? (lambda (s)
 			       (i-heuristic s mas-goal))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;; The puzzles below are for the "bonus" problem (#10)
;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; 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))