A problem about 3*3 puzzle

shaill · Posted: Tue Nov 15, 2005 7:08 pm Post subject: A problem about 3*3 puzzle

Hello, because my teacher give me a programming homework,
like
8 7 4
1 5 6
2 3 S S means space (like this game http://www.permadi.com/java/puzzle8/)
write a program to figure out the standard form
standard form
1 2 3
4 5 6
7 8 S
We has to print the steps between the process.

I use the recursive to let PC run itself.
But I spend lots of time.And didn't figure out sometimes.
I didn't use any algorithm.
for example,(position 0 1 2
3 4 5
6 7 8 )
if space is now at position 0
I just the following recursive

newNode=swap(&present,3); //change to position 3
startPuzzle(newNode,depth);
newNode=swap(&present,1);
startPuzzle(newNode,depth);

space position 3
newNode=swap(&present,1); //change to position 1
startPuzzle(newNode,depth);
newNode=swap(&present,4);
startPuzzle(newNode,depth);
newNode=swap(&present,6);
startPuzzle(newNode,depth);

LOOK!! from position 0 -> 1 ->0 ->1 ....
it CIRCLE....

startPuzzle is my recursive functions

It is really inefficient.
And sometimes it will be stuck or circle by the other space position's recursive.

SO,PLEASE tell me the algoritm or recursive sequence...
I am so tired...Please help..thank u...