;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; CSCI--4150 Introduction to Artificial Intelligence
; Sliding Block Puzzles, Version 1.2
; Copyright (C) 2002-2005 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.
; These are mostly easy puzzles, so your Manhattan-distance heursistic
; should work well for these problems.
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(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)
  (solve ep1-start ep1-goal? (lambda (s)
			       (manhattan-dist s ep1-goal))))

(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)
  (solve ep2-start ep2-goal? (lambda (s)
			       (manhattan-dist s ep2-goal))))

(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)
  (solve ep3-start ep3-goal? (lambda (s)
			       (manhattan-dist s ep3-goal))))

(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)pp
  (solve ep4-start ep4-goal? (lambda (s)
			       (manhattan-dist s ep4-goal))))

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

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

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

(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, mostly simple puzzles.
; 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(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 (a-hughes)
  (solve hughes-start hughes-goal? (lambda (s)
				     (a-heuristic s hughes-goal))))
(define (i-hughes)
  (solve hughes-start hughes-goal? (lambda (s)
				     (i-heuristic s hughes-goal))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Here's some puzzles that I made up.
; 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(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))


(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 (a-w1)
  (solve w1-start w-goal? (lambda (s) (a-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 (a-w2)
  (solve w2-start w-goal? (lambda (s) (a-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 (a-w3)
  (solve w3-start w-goal? (lambda (s) (a-heuristic s w-goal))))
(define (i-w3)
  (solve w3-start w-goal? (lambda (s) (i-heuristic 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))

(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 (a-mas)
  (solve mas-start mas-goal? (lambda (s) (a-heuristic s mas-goal))))
(define (i-mas)
  (solve mas-start mas-goal? (lambda (s) (i-heuristic s mas-goal))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; More puzzles that I made up.
; 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

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

;;;
(define y1-start '((f f a empty empty)
		   (f f b empty empty)
		   (c d p p p)
		   (e e q q p)))
(define (y1)
  (solve y1-start y-goal? (lambda (s) (manhattan-dist s y-goal))))
(define (y1^2)
  (solve y1-start y-goal? (lambda (s) (square (manhattan-dist s y-goal)))))
(define (a-y1)
  (solve y1-start y-goal? (lambda (s) (a-heuristic s y-goal))))
(define (i-y1)
  (solve y1-start y-goal? (lambda (s) (i-heuristic s y-goal))))

;;;
(define y2-start '((a a empty empty empty)
		   (b c empty d d)
		   (p p p d d)
		   (e f p q q)))
(define (y2)
  (solve y2-start y-goal? (lambda (s) (manhattan-dist s y-goal))))
(define (y2^2)
  (solve y2-start y-goal? (lambda (s) (square (manhattan-dist s y-goal)))))
(define (a-y2)
  (solve y2-start y-goal? (lambda (s) (a-heuristic s y-goal))))
(define (i-y2)
  (solve y2-start y-goal? (lambda (s) (i-heuristic s y-goal))))

;;;
(define y3-start '((empty empty a b b)
		   (empty empty c d d)
		   (p p p d d)
		   (e f p q q)))
(define (y3)
  (solve y3-start y-goal? (lambda (s) (manhattan-dist s y-goal))))
(define (y3^2)
  (solve y3-start y-goal? (lambda (s) (square (manhattan-dist s y-goal)))))
(define (a-y3)
  (solve y3-start y-goal? (lambda (s) (a-heuristic s y-goal))))
(define (i-y3)
  (solve y3-start y-goal? (lambda (s) (i-heuristic s y-goal))))


;;;
(define y4-start '((a a empty b b)
		   (empty empty empty d d)
		   (p p p d d)
		   (e f p q q)))
(define (y4)
  (solve y4-start y-goal? (lambda (s) (manhattan-dist s y-goal))))
(define (y4^2)
  (solve y4-start y-goal? (lambda (s) (square (manhattan-dist s y-goal)))))
(define (a-y4)
  (solve y4-start y-goal? (lambda (s) (a-heuristic s y-goal))))
(define (i-y4)
  (solve y4-start y-goal? (lambda (s) (i-heuristic s y-goal))))

;;;
(define y5-start '((a a empty b b)
		   (empty empty empty c c)
		   (p p p q q)
		   (e f p d d)))
(define (y5)
  (solve y5-start y-goal? (lambda (s) (manhattan-dist s y-goal))))
(define (y5^2)
  (solve y5-start y-goal? (lambda (s) (square (manhattan-dist s y-goal)))))
(define (a-y5)
  (solve y5-start y-goal? (lambda (s) (a-heuristic s y-goal))))
(define (i-y5)
  (solve y5-start y-goal? (lambda (s) (i-heuristic s y-goal))))

;;;
(define y6-start '((a a empty b b)
		   (empty empty empty c c)
		   (p p p q q)
		   (e f p d d)))
(define (y6)
  (solve y6-start y-goal? (lambda (s) (manhattan-dist s y-goal))))
(define (y6^2)
  (solve y6-start y-goal? (lambda (s) (square (manhattan-dist s y-goal)))))
(define (a-y6)
  (solve y6-start y-goal? (lambda (s) (a-heuristic s y-goal))))
(define (i-y6)
  (solve y6-start y-goal? (lambda (s) (i-heuristic s y-goal))))

;;;
(define y7-start '((a a empty empty empty)
		   (q q empty c d)
		   (p p p  b b)
		   (e e p f f)))
(define (y7)
  (solve y7-start y-goal? (lambda (s) (manhattan-dist s y-goal))))
(define (y7^2)
  (solve y7-start y-goal? (lambda (s) (square (manhattan-dist s y-goal)))))
(define (a-y7)
  (solve y7-start y-goal? (lambda (s) (a-heuristic s y-goal))))
(define (i-y7)
  (solve y7-start y-goal? (lambda (s) (i-heuristic s y-goal))))






;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;
;;; Challenge puzzles!
;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


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


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; Yet more puzzles that I made up...
; 
; 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)))
(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 2x1 block (E) under the 2x2 block (Q) was drawn in the
; middle (straddling two columns).  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 this heuristic but here it is
(define (century^2)
  (solve century-start
	 century-goal?
	 (lambda (s)
	   (square (manhattan-dist s century-goal)))))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; the "super century" puzzle by Gil Dogon
; requires 134 moves
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define super-century-start '((  A     B   C D)
			      (  A     E   Q Q)
			      (  F     E   Q Q)
			      (  F     G   G H)
			      (empty empty I I)))
(define super-century-goal '((#f #f #f #f)
			     (#f #f #f #f)
			     (#f #f #f #f)
			     (#f  Q  Q #f)
			     (#f  Q  Q #f)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; the "quzzle" puzzle by Jim Lewis
; the hardest (?) simplest (?) sliding block puzzle (supposedly)
; requires 84 moves
;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define quzzle-start '((  Q     Q   A A)
		       (  Q     Q   B C)
		       (empty empty B C)
		       (  D     E   E F)
		       (  D     G   G H)))

(define quzzle-goal '((#f #f  Q  Q)
		      (#f #f  Q  Q)
		      (#f #f #f #f)
		      (#f #f #f #f)
		      (#f #f #f #f)))

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;
; "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 which is in
; the support code.
;
(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))