Moving N Kings on chess board

Suppose we have a chessboard (of arbitrary size) and N kings initially placed on N squares. Let's suppose now we select N new squares to move the kings to through a sequence of legal moves (no collisions). The goal would be to minimize the total distance moved by all kings. I can't really think of an algorithm/adaptation that could handle moving all pieces while taking care of preventing "colliding" kings. The algorithm should be faster than recursively selecting target squares and selecting the minimum transport. I'm hopeful someone has invaluable advice on this problem.

Thanks

Solution

First, you need to find a minimum total distance complete bipartite matching between all the kings and all the target squares. You can recast this as a maximum weight bipartite matching by replacing each distance with weight (something_big-distance), and then finding a maximum weight bipartite matching, or you can just maintain the invariant that the matching is complete and find the minimum bipartite matching directly.

I think the easiest way to do this is with the Edmonds-Karp Algorithm. This is normally used for finding a maximum flow, but maximum weight bipartite matching is essentially an instance of that problem, once you add single source and sink vertices.

Once you've found the matching between kings and their target squares, you can move the kings. It doesn't make a lot of difference what order you make them in as long as you move each king along its shortest path, and you don't move a king onto an already occupied square. If a king wants to move onto an occupied square, there are two choices:

If the king-in-the-way is not already at its target square, then just move that one instead.
If the king-in-the-way is already on its target square, then swap targets between the king you want to move and the king-in-the-way. Then just move the king-in-the-way. This doesn't change the total number of moves you have to make.

Of course, the king-in-the-way might also have a king in its way, so apply these rules again until you get to one you can move.

Now you might be wondering about what to do if every king that has to move has a king it its way. That could only happen if there's a cycle where all the kings want to move around the cycle... but this cannot happen.

Moving all the kings around a cycle costs moves, but it doesn't change the state of the board. Such a condition would therefore imply that the set of paths you found in your original mapping are not minimal. Since they are minimal, such a condition is impossible.