11198 - Dancing Digits

[sunshine12]

i still dont get it..

[brianfry713]

http://en.wikipedia.org/wiki/Breadth-first_search
Suppose the initial digits are:
1 2 4 5 6 7 -3 8
Put the initial digits onto the queue and also keep track of the number of moves.

Pop the front of the queue
Iterate through all pairs of digits until you find a pair where one is positive and one is negative and the sum of the absolute values is prime. Those pairs are: 2 and -3, 4 and -3, -3 and 8.
For each pair, generate all the possible moves: female to the left of the male, female to the right of the male, male to the left of the female, male to the right of the female.
So for pair 2 and -3, the possible moves are:
1 -3 2 4 5 6 7 8 (-3 to 2's left)
1 2 -3 4 5 6 7 8 (-3 to 2's right, this one ends up sorted)
1 4 5 6 7 2 -3 8 (2 to -3's left)
1 4 5 6 7 -3 2 8 (2 to -3's right)
Put each new state to the end of the queue.
Do the same with the other pairs 4 and -3, -3 and 8
Continue until you reach a sorted state or the queue is empty