Asking for algorithm to find N Knights global shortest path

Question

I've stampled upon a curious problem.

I've got an unbounded chessboard, N knights starting locations and N target locations.

The task is to find minimal number of moves for all knights to reach all target locations.

I know that shortest path problem for a single knight can be solved using breadth-first search, but how can it be solved for multiple knights?

Sorry for my english, I use it seldom.

Answer 1

I assume you know how to do it for one Knigt .

You can reformulate your problem as a linear program:

I will use the following notations :

We have N knights and N en locations.

xij = 1 if you chose knight i to go to location j and 0 otherwise

cij is the min length of moving knight i to location j

Then you have the following linear program :

variables:

xij for i j in [0,N]

Cost function :

C= SUM(cij.xij for (i,j) in [0,N]x[0,N])

constraints:

SUM(xij for j in [1,N]) = 1 //exactly one knigt goes from i to j

SUM(xij for i in [1,N] ) = 1

(The matrix (xij) is a stochastic matrix)

if X is the matrix of (xij) you have n! possible matrix. This problem can be NP-Hard (there is no easy solution to this system, solving the system is pretty similar than testing all possible solutions).

---

EDIT:

This problem is called the assignment problem and there exist multiple algorithms to solve it in polynomial time . (check out @purav answer for an example)

As mentionned by @Purav even though this kind of problems can be NP-hard, in this case it can be solve in O(n^3)

---

---

---

About the problem @j_random_hacker raised :

Problem

If a knight is at a endpoint, the next knights should not be able to go through this endpoint. So the Cij might need to be updated after each knight is moved.

Remarks :

1. multiple optimal paths :

As there is no constraint on the side of the chessboard (ilimited chessboard), the order in which you do your move for achiveing the shortest path is not relevant, so there is always a lot a different shortest path (I won't do the combinatorics here).

Example with 2 knights

Let say you have 2 K and 2 endpoints ('x'), the optimal path are drawned.

    -x
   |
   | 
   x
   |
K-- --K

you move the right K to the first point (1 move) the second cannot use the optimal path.

    -x
   |
   |  
   K
   |
K-- --:

But I can easily create a new optimal path, instead of moving 2 right 1 up then 2 up 1 right. 1 can move 2 up 1 right the 1 up 2 right (just inverse)

   --K
  |
 -    
|   K
|   |
:    --:

and any combination of path works :

1 U 2 R then 2 U 1 R etc... as long as I keep the same number of move UP LEFT DOWN and RIGHT and that they are valid.

2. order in which knights are moved :

The second thing is that I can chose the order of my move.

example:

with the previous example if I chose to start with the left knight and go to the upper endpoint, dont have anymore endpoint constraint.

    -K
   |
   | 
   x
   |
:-- --K


    -K
   |
   | 
   K
   |
:-- --:

With these 2 remarks it might be possible to prove that there is no situation in which the lower bound calculated is not optimal .

Answer 2

You can compute the cost matrix as suggested by Ricky using breadth first search. so now, cost[i][j] denotes the cost of choosing knight i to goto end location j. Then you can use the Hungarian algorithm to find the final answer, which can be computed in O(N^3) complexity.

Answer 3

BFS can still work here. You need to adjust your states a bit, but it will still work:

let S be the set of possible states:
S={((x1,y1),(x2,y2),...,(xn,yn))|knight i is in (xi,yi)}

For each s in S, define:
Successors(s)={all possible states, moving 1 knight on the board}

Your target states are of course all permutations of your target points [you don't actually need to develop these permutations, just check if you reached a state where all the squares are "filled", which is simple to check]

start=(start_1,start_2,...,start_n) where start_i is the start location of knight i.

A run of BFS, from start [the initial position of each knight], is guaranteed to find a solution if one exists [because BFS is complete]. It is also guaranteed to be the shortest possible solution.

(*) Note that the case for single knight is a private instance of this solution, with n=1.

Though BFS will work, it will take a lot of time! the branch factor in here is 4n, so the algorithm will need to develop O((4n)^d) vertices, where n is the number of knights and d is the number of steps needed for a solution.

Possible optimizations:

1. Space: Note that because BFS uses a lot of memory [O((4n)^d)] you might want to use Iterative Deepening DFS, which behaves like a BFS, but consumes much less memory [O(nd)], but takes more time to run.
2. Time: To accelerate the solution search, you can use A Star with an admissible heuristic function. It is also guarenteed to find a solution if one exists, and also ensures the solution found is optimal, and will probably [with good heuristic] need to develop less vertices then BFS.

Answer 4

So, I've found the solution.

BFS won't work well on an unlimited chessboard. There is no point in using any shortest path algorithm -- number of knight's moves from location a to location b can be computed in O(1) time -- M. Deza, Dictionary of Distances, p. 251

http://www.scribd.com/doc/53001767/Dictionary-of-Distances-M-Deza-E-Deza-Elsevier-2006-WW

The assignment problem can be solved using mincost-maxflow algorithm (eg. Edmonds-Karp):

http://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm