given the place of two knights on a chess board what is the minimum steps to swap their places? note that
- they are moving in turns i.e. the white moves first then the black etc.
- they can't -at the same time -be on the same square because they will eat each other.
how to find a general solution to find the minimum steps required ?
i have already written code that finds the minimum steps to reach a target, also used this to write the code that determine where two knights meet and how many steps but i don't know how to start to solve the above problem!
how to find the route for both knights?
usually in knight destination problem we would save the previews location while doing the breads first search, but in this problem since they can't be at the same time in the same square the above technique can't guarantee this!!
If one knight follows the same path as the other, but in reverse, at some point in time they will be one move apart and the next move will cause them to collide. (The case where they start at a1 and b3 is just one example of this.)
So you need two distinct paths. In cases where you have two paths of the same length without backtracking, you also need to avoid these two cases: paths of even length that intersect on a square at the halfway point of each path; paths of odd length such that the "halfway" moves (the moves with equal numbers of moves before and after) use the same two squares. Of course we also need to be able to assign the paths so as to avoid collisions on any other square as well.
A case where two shortest paths collide at the midway point occurs with the paths between a1 and g1: there are four paths of length $4$ that pass through d4. There are also several paths of length $4$ that do not pass through d4, so the minimum number of moves is $8.$
A case where two shortest paths use the same two squares for the "halfway" move occurs with the paths between a3 and h3: there are four paths of length $5$ where the third move is between d2 and e4; but there are several paths that don't use those two squares, so the minimum number of moves is $10.$
I think all such cases can be resolved similarly to these, but of course it is another matter to prove this.
If one path is shorter than the other then one of the knights can insert extra moves in its path by moving to some other square and back again. Again, to prove that this will always be possible is another matter, of course.
On a finite chessboard, the edges can block some paths that would have been possible on an infinite board. For example, with the knights starting at $(1,1)$ and $(3,1)$ (aka a1 and c1), on an infinite board one knight could move to $(2,3)$ and the other could move to $(2,-1)$, but on a regular $8\times8$ board the only two-move path goes through b3.
Assuming the pieces must move in strict alternation, never moving the same piece twice consecutively, the number of moves is twice the length of the second-shortest path between the given squares on the given chessboard (provided that the conjectures above are true). For example, starting at a1 and c1, one knight can take the path through b3, but the other must take a different path, whose length must be at least $3,$ so a minimum of $6$ moves are required.