Then, it comes down to figuring out the optimal set of swaps.

... but the key to that is that there is not 1 optimal sequence of swaps, but rather multiple equivalent ones.

This comes from the fact that you can re-order some of the swaps in an optimal sequence and still have an optimal sequence.

So, the key is to figure out which swaps have to be in any optimal sequence, and then do those first.

Specifically:

1. If there is only one of a given letter in the puzzle (or only one left), then move that directly to its destination space.
2. If there are two letters that are each in the other's destination (e.g. an "a" where there needs to be a "b" and a "b" where there needs to be an "a", then swap those.
3. If every one of a given letter needs to be swapped with the same letter (e.g. every "a" is in a space that should contain a "b", or every "a" is supposed to go to a space that currently has a "b"), then you can just move all of those letters to their given destination.

Go through these steps repeatedly, and as you do new opportunities to apply these same steps show up, so you apply them again.

This will almost always get you to a solved puzzle.

The ones where it doesn't wind up taking you to a simple enough state that you can just solve the remaining swaps by brute force.