;;;
;;;                 |               |
;;;          Engine 1               5
;;;                 | ______3______ |
;;;                 |/             \|
;;;                 |               |
;;;               A 2               4 B
;;;                 |               |
;;;                  \___Tunnel____/
;;;
;;; Puzzle:
;;;   Refer to the diagram above representing a small railway.
;;;   Given an engine at point 1, a carriage A at point 2, and a
;;;   carriage B at point 4.  Given the restriction that the engine
;;;   can go through the tunnel but cars cannot.  Given the usual
;;;   other restrictions such as carriages cannot propel themselves,
;;;   the engine cannot move through, over, or around a carriage, and
;;;   no railway engines or carriages can move directly across the two
;;;   open ends of a switch track.  How can the engine switch the
;;;   position of the carriages and return to its starting position?
;;;
;;; Tracks:
;;;   The track sections are numbered from 1 to 5 as in the diagram above.
;;;
;;; Objects:
;;;   The engine, carriage A, and carriage B are called "objects."
;;;   Objects occupy track positions (1-5) uniquely.  We call the
;;;   engine 'e, the A carriage 'a and the B carriage 'b.
;;;
;;; States:
;;;   State of layout is a list of five lists.  Each of five lists represents
;;;   a situation on a track.  The first list shows what is happening on
;;;   track 1, the second list shows track 2, and so on.  Each list contains
;;;   the objects on the corresponding section of track.  The order of
;;;   objects given in each list, from left to right, is what it would be
;;;   moving clockwise around any section of track.  For example, the
;;;   following pictures match the corresponding states:
;;;
;;;   'a          |                         |          |
;;;   'b          |                         |          |
;;;   'e          |  '((e b a)()()()())     |          |  '(()(e b a)()()())
;;;    | ________ |                         | ________ |
;;;    |/        \|                         |/        \|
;;;    |          |                        'a          |
;;;    |          |                        'b          |
;;;    \__Tunnel__/                         'e_Tunnel__/
;;;
;;;    |          |                         |          |
;;;    |          |                         |          |
;;;    |          |  '(()()(e b a)()())     |          |  '(()()()(e b a)())
;;;    | _'e'b'a_ |                         | ________ |
;;;    |/        \|                         |/        \|
;;;    |          |                         |         'e
;;;    |          |                         |         'b
;;;    \__Tunnel__/                         \_Tunnel_'a
;;;
;;;    |         'e
;;;    |         'b
;;;    |         'a  '(()()()()(e b a))
;;;    | ________ |
;;;    |/        \|
;;;    |          |
;;;    |          |
;;;    \__Tunnel__/
;;;
;;; 
;;;   The Start state is '((e)(a)()(b)())
;;;   The Goal or Final state is '((e)(b)()(a)())

'((e a b)()()()()) '((e a)(b)()()()) '((e a)()(b)()()) '((e a)()()(b)()) '((e a)()()()(b))
'((e)(a b)()()()) '((e)(a)(b)()()) '((e)(a)()(b)()) '((e)(a)()()(b))
'((e)()(a b)()()) '((e)()(a)(b)()) '((e)()(a)()(b))
'((e)()()(a b)()) '((e)()()(a)(b))
'((e)()()()(a b))
'(()(e a b)()()()) '(()(e a)(b)()()) '(()(e a)()(b)()) '(()(e a)()()(b))
'(()(e)(a b)()()) '(()(e)(a)(b)()) '(()(e)(a)()(b))
'(()(e)()(a b)()) '(()(e)()(a)(b))
'(()(e)()()(a b))
'(()()(e a b)()()) '(()()(e a)(b)()) '(()()(e a)()(b))
'(()()(e)(a b)()) '(()()(e)(a)(b))
'(()()(e)()(a b))
'(()()()(e a b)()) '(()()()(e a)(b))
'(()()()(e)(a b))
'(()()()()(e a b))
         ;;
'((e b a)()()()()) '((e b)(a)()()()) '((e b)()(a)()()) '((e b)()()(a)()) '((e b)()()()(a))
'((e)(b a)()()()) '((e)(b)(a)()()) '((e)(b)()(a)()) '((e)(b)()()(a))
'((e)()(b a)()()) '((e)()(b)(a)()) '((e)()(b)()(a))
'((e)()()(b a)()) '((e)()()(b)(a))
'((e)()()()(b a))
'(()(e b a)()()()) '(()(e b)(a)()()) '(()(e b)()(a)()) '(()(e b)()()(a))
'(()(e)(b a)()()) '(()(e)(b)(a)()) '(()(e)(b)()(a))
'(()(e)()(b a)()) '(()(e)()(b)(a))
'(()(e)()()(b a))
'(()()(e b a)()()) '(()()(e b)(a)()) '(()()(e b)()(a))
'(()()(e)(b a)()) '(()()(e)(b)(a))
'(()()(e)()(b a))
'(()()()(e b a)()) '(()()()(e b)(a))
'(()()()(e)(b a))
'(()()()()(e b a))           
         ;;
'((b e a)()()()()) '((b e)(a)()()()) '((b e)()(a)()()) '((b e)()()(a)()) '((b e)()()()(a))
'((b)(e a)()()()) '((b)(e)(a)()()) '((b)(e)()(a)()) '((b)(e)()()(a))
'((b)()(e a)()()) '((b)()(e)(a)()) '((b)()(e)()(a))
'((b)()()(e a)()) '((b)()()(e)(a))
'((b)()()()(e a))
'(()(b e a)()()()) '(()(b e)(a)()()) '(()(b e)()(a)()) '(()(b e)()()(a))
'(()(b)(e a)()()) '(()(b)(e)(a)()) '(()(b)(e)()(a))
'(()(b)()(e a)()) '(()(b)()(e)(a))
'(()(b)()()(e a))
'(()()(b e a)()()) '(()()(b e)(a)()) '(()()(b e)()(a))
'(()()(b)(e a)()) '(()()(b)(e)(a))
'(()()(b)()(e a))
'(()()()(b e a)()) '(()()()(b e)(a))
'(()()()(b)(e a))
'(()()()()(b e a))           
         ;;
'((b a e)()()()()) '((b a)(e)()()()) '((b a)()(e)()()) '((b a)()()(e)()) '((b a)()()()(e))
'((b)(a e)()()()) '((b)(a)(e)()()) '((b)(a)()(e)()) '((b)(a)()()(e))
'((b)()(a e)()()) '((b)()(a)(e)()) '((b)()(a)()(e))
'((b)()()(a e)()) '((b)()()(a)(e))
'((b)()()()(a e))
'(()(b a e)()()()) '(()(b a)(e)()()) '(()(b a)()(e)()) '(()(b a)()()(e))
'(()(b)(a e)()()) '(()(b)(a)(e)()) '(()(b)(a)()(e))
'(()(b)()(a e)()) '(()(b)()(a)(e))
'(()(b)()()(a e))
'(()()(b a e)()()) '(()()(b a)(e)()) '(()()(b a)()(e))
'(()()(b)(a e)()) '(()()(b)(a)(e))
'(()()(b)()(a e))
'(()()()(b a e)()) '(()()()(b a)(e))
'(()()()(b)(a e))
'(()()()()(b a e))
         ;;
'((a b e)()()()()) '((a b)(e)()()()) '((a b)()(e)()()) '((a b)()()(e)()) '((a b)()()()(e))
'((a)(b e)()()()) '((a)(b)(e)()()) '((a)(b)()(e)()) '((a)(b)()()(e))
'((a)()(b e)()()) '((a)()(b)(e)()) '((a)()(b)()(e))
'((a)()()(b e)()) '((a)()()(b)(e))
'((a)()()()(b e))
'(()(a b e)()()()) '(()(a b)(e)()()) '(()(a b)()(e)()) '(()(a b)()()(e))
'(()(a)(b e)()()) '(()(a)(b)(e)()) '(()(a)(b)()(e))
'(()(a)()(b e)()) '(()(a)()(b)(e))
'(()(a)()()(b e))
'(()()(a b e)()()) '(()()(a b)(e)()) '(()()(a b)()(e))
'(()()(a)(b e)()) '(()()(a)(b)(e))
'(()()(a)()(b e))
'(()()()(a b e)()) '(()()()(a b)(e))
'(()()()(a)(b e))
'(()()()()(a b e))           
;;
'((a e b)()()()()) '((a e)(b)()()()) '((a e)()(b)()()) '((a e)()()(b)()) '((a e)()()()(b))
'((a)(e b)()()()) '((a)(e)(b)()()) '((a)(e)()(b)()) '((a)(e)()()(b))
'((a)()(e b)()()) '((a)()(e)(b)()) '((a)()(e)()(b))
'((a)()()(e b)()) '((a)()()(e)(b))
'((a)()()()(e b))
'(()(a e b)()()()) '(()(a e)(b)()()) '(()(a e)()(b)()) '(()(a e)()()(b))
'(()(a)(e b)()()) '(()(a)(e)(b)()) '(()(a)(e)()(b))
'(()(a)()(e b)()) '(()(a)()(e)(b))
'(()(a)()()(e b))
'(()()(a e b)()()) '(()()(a e)(b)()) '(()()(a e)()(b))
'(()()(a)(e b)()) '(()()(a)(e)(b))
'(()()(a)()(e b))
'(()()()(a e b)()) '(()()()(a e)(b))
'(()()()(a)(e b))
'(()()()()(a e b)))))

;;; Movement:
;;;   representation of the action is one state at a time involving the
;;;   movement of the engine from one section of track to an adjacent
;;;   section of track.  The following shows the list of adjacent pairs
;;;   of track sections: 1-2, 2-3, 2-4, 3-4, 4-5.  Section 1 is not adjacent
;;;   to sections 3 or 5.  Section 3 is not adjacent to section 5.
;;;   A "move" from one state to another is assumed to involve all carriages
;;;   either attached to the engine or pushed by it.  Thus, if the engine
;;;   is attached to carriages A and B, is clockwise from A and B and is 
;;;   moving clockwise, then the next state shows the engine and all
;;;   carriages in the next section of track, clockwise from the previous
;;;   section.  That is, a train does not straddle track sections in any
;;;   state.
;;;
;;; Plan:
;;;   Keep a list of states, called a history.  The history at the outset
;;;   is the Start state above.  Try to extend the history using legal
;;;   "next states" in such a way that no state in the history is repeated.
;;;   Finish when the Goal state is added to the history.  Output the history.
;;;