Knight captures queen and rook in minimum moves

Question

You are given a chess board containing a knight, rook and queen. You should determine the minimal number of moves the knight needs to capture both the rook and the queen, assuming neither of them moves. You may capture them in either order - rook first or queen first.

Complete problem statement.

In this task, can it be proven that path from the knight to the rook plus the path from the rook to the queen is equal/smaller/bigger than the path from the knight to the queen plus the path from the queen to the rook? Or I must compute them both and take the minimum?

Answer 1

Since the starting positions are all arbitrary, the Queen and Rook could theoretically be swapped to generate an alternate version of the same problem. Thus, you can't assume one way is shorter than the other by default, you have to calculate them both. It doesn't matter which one is which, but all 3 distances are relevant.

The following is only relevant if you want to implement an intelligent algorithm instead of a breadth search.

Note that there are a total of 4 possible paths (K is Knight, R is Rook, Q is queen):

1. K -> R -> Q
2. K -> Q -> R
3. K -> R -> K -> Q
4. K -> Q -> K -> R

You need the minimum between these 4. So if you computed distances

a = K -> Q
b = K -> R
c = R -> Q

then you're looking for the minimum between a+c, b+c, 2*a+b and 2*b+a.
If you calculate your distance in a sufficiently robust way, the paths 3 and 4 become obsolete because they have a greater or the same length as 1 and 2, respectively. However, if you're unsure, you can use them to confirm the results. If 3 or 4 is the shortest path, it has to be exactly as long as 1 or 2 if your algorithm works correctly.

Answer 2

You must compute the minimum of knight to rook and knight to queen.

The path from queen to rook is equal to the path from rook to queen, so you only need to compute that one way.