Exhaustive Search

An exhaustive search of all possible moves would be difficult to write and will not finish in time, so another strategy is needed. Perhaps a breadth first search would work in some cases, but still in the worst case would still have a bad running time and memory requirements. As a ballpark estimate, in the worst case you have to consider ~8~ swaps for each square, giving you ~8^9~ combinations (more than ~130~ million) to try.

Observations

If you can find a fast enough way to transform a ~3 \times 3~ square into one of the magic squares, you can just run it ~8~ times – once for each of the eight possible magic squares – and look for the smallest required number of moves.

There is an upper bound of ~9~ moves for transforming any ~3 \times 3~ square that has no blanks into any given magic square. This is because every swap can be used to put at least one number in its correct spot. In fact, there is no faster approach when there are no blanks than to simply cycle through all nine spots and swap the correct piece into place if necessary.

It actually does not matter to the number of moves required whether you fill in the blanks at the beginning or at the end.

Final Strategy

Try each of the ~8~ magic squares. For each one, you transform the given ~3 \times 3~ square by first swapping into place as many pieces as you can, and then by filling in the blanks at the end with their correct numbers. Whichever of the ~8~ squares requires the least moves gives you the answer.