How would you propose to change the algorithm to come to a short solution fast?!

I haven't looked at your code, just read your description. However, the classical way is to do breadth-first, instead of depth-first. Outline:

• 0. Let the starting position be P^S. Let k be 0. Goto 15 if P^S is a solution.
• 1. Keep a cache C of "seen" positions.
• 2. Keep a fifo queue Q of "todo" positions, with their move number.
• 3. Push tuple (P^S, 1) onto Q.
• 4. If Q is empty, goto 14.
• 5. Shift first tuple of Q. Let this be (P, k).
• 6. Calculate all possible moves of position P. Call this set of moves M. Unless the starting position doesn't allow for any moves, M will never be empty.
• 7. If M is empty, goto 4.
• 8. Remove a move m from M. Apply m to P, yielding postion P'.
• 9. If P' in C, goto 7.
• 10. If P' is a solution, goto 15.
• 11. Add P' to C.
• 12. Push tuple (P', k+1) on Q. (So this tuple will be inserted at the end).
• 13. Goto 7.
• 14. Terminate unsuccesfully. (No solution possible).
• 15. Terminate with success. Minimum number of moves is k.

In fact, this is just Dijkstra's algorithm applied on a graph where each vertex of the graph is a possible position of the puzzle, and there's an edge between two positions one can go from one position to the other in a single move.

I leave it up to the reader to turn the TAOCP style of describing the algorithm into a "real" program.

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.