0

given the place of two knights on a chess board what is the minimum steps to swap their places? note that

  1. they are moving in turns i.e. the white moves first then the black etc.
  2. 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!!

Community
  • 1
Amr
  • 103
  • 1
    Suppose they start one knight's move apart. Are you allowed to use just four moves $A,B,A,A$ or are the two knights required to make equal numbers of moves. In that case, the minimum would be 6. – almagest Jan 04 '20 at 17:58
  • If they start two knight's moves apart, the minimum is brought down to four. – Andrew Chin Jan 04 '20 at 18:54
  • You can brute force configurations in which the knights are close, and use Dijkstra onwards. – ViHdzP Jan 05 '20 at 07:43
  • @almagest yes if they one move apart the total moves for both would be 6 (3 for the white and 3 for the black), also they required to move in turns, just like the normal chess. – Amr Jan 05 '20 at 10:21
  • @AndrewChin no it's 3 for each knight! – Amr Jan 05 '20 at 10:22
  • It'd be two for each knight if, for example, White knight started on e4 and Black on b5. – Andrew Chin Jan 05 '20 at 16:51
  • @AndrewChin but in this position they aren't one step apart when white on e4, black on c5 – Amr Jan 05 '20 at 18:57
  • I know that; read my initial comment. – Andrew Chin Jan 05 '20 at 18:59

1 Answers1

1

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.

David K
  • 98,388
  • Getting the second shortest path would be by getting the shortest path for the second knight avoiding the square of collide - in which the next move for one of them will be at the same square where the other lies- Yes? – Amr Jan 06 '20 at 12:36
  • If I understand you, that's almost correct. Note that when the initial positions are a1 for white and b3 for black, if white takes the shortest path then white's next move is b3, which then becomes the "square of collision". It is actually white (not black) who must take the second shortest path (a1 c2 d4 b3) in order to avoid the collision. – David K Jan 06 '20 at 12:44