Just thinking out loud, this feels like a problem for a brute force recursive search. You'd be able to try all of the possible swaps, and at each step bail if you run into a case where you're repeating a swap to prune the search space (hopefully this is a heavy pruning). Each step along the way you see if everyone's back in their correct bodies - when you hit that you just return out of the recursive calls printing the moves used along the way.
Something like
Code:
swap(this_source, this_dest, body array, swap scorecard)
{
if swap was already tried, return invalid
swap this_source with this_dest, update records to show that this swap happened
if everyone is where they should be, return valid (this is the end of the search)
for each source 0..body array length-1
for each dest 0..body array length - 1
{
if ((source != dest) && (swap(source, dest, ...) == valid))
{
print this swap (or push it on a result stack to reverse the order it is printed)
return valid
}
}
}
If this brute force search runs too slowly, you'll have to be smarter about how you explore the search space. Instead of iterating through all combinations of source and dest in order, you'll need a way to weight them as more or less likely to lead to a solution and try those first.
This reminds me a bit of the 8/15/whatever-puzzle problem, except in this case you can swap any two elements instead of just ones around the spaces. Since that opens up the search space considerably, solutions to that problem may or may not transfer over, but at least it gives you an idea of where to start to look for ideas.
