0
$\begingroup$

BFS Algorithm for Finding Minimum Steps for Knight Eliminating a Moving Pawn.

As the Title suggests, I'm trying to intuitively understand this problem. Suppose we have a Pawn and a Knight taking turns. Both pieces must move on their turn, and both pieces have a starting position, and suppose the board is sufficiently large enough for the Knight to eventually catch up to and eliminate the Pawn, where the Pawn is avoiding being captured. I want to find the minimum amount of moves the Knight takes to eliminate the Pawn.

I know that we can use a BFS algorithm to find the shortest path between the Knight and a stationary spot on the board, but I'm not sure how to do this for a moving target. What if we do a BFS on every square of the column the Pawn is travelling on and then compare the number of moves that takes and check if one of these sequence of moves ends up on the Pawn's location. But this doesn't seem like it will always work, because finding the minimum amount of moves to where the Pawn will eventually be could be less than the actual minimum amount of moves to catch up to the Pawn because the Knight could "stall" a bit until it's in the right position to eliminate the Pawn.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Nice question. "The Knight could 'stall' a bit". There lies the clue to how to solve the problem. Instead of just computing the minimum amount of moves for the Knight to reach each position in front the pawn, what you should compute is all possible numbers of moves to reach each position. $\endgroup$
    – John L.
    Mar 31, 2019 at 15:33
  • $\begingroup$ What do you mean by minimum amount of moves for the Knight? Is the Pawn cooperating in being captured or trying to avoid capture? Is this a minimax kind of problem? $\endgroup$
    – D.W. ♦
    Mar 31, 2019 at 18:48
  • $\begingroup$ @D.W. The Pawn is avoiding being captured. The idea is that the Pawn and Knight start on arbitrary squares, and each piece takes turns moving. $\endgroup$
    – HoopsMcCann
    Mar 31, 2019 at 19:46
  • $\begingroup$ OK. Thanks. On further reflection, it looks like there is no difference as the Pawn has no choice about how to move -- it is forced to move forward one square on every move. $\endgroup$
    – D.W. ♦
    Mar 31, 2019 at 19:52

2 Answers 2

Reset to default
1
$\begingroup$

It's very simple.

A pawn has a choice to move one or two positions forward in its first move, in all following moves it moves one position. A knight moves two squares in one direction, and one step orthogonal.

As a result, the colour of a pawn's square changes on every move, except on the first move, where it has a choice to change the square's colour or not. The knight always changes the colour of its square. So in its first move, the pawn moves to the same colour as the knight, and from then on, the knight can never take the pawn.

(You need to specify what should happen if the knight is in the pawn's way so it cannot move though. If the rule is that the pawn just doesn't move, then the knight can block the pawn's path, and two moves later takes the pawn).

Improve this answer
$\endgroup$
0
$\begingroup$

Form a graph where each vertex is a pair $(k,p)$ where $k$ represents the position of the knight and $p$ represents the position of the pawn; each edge represents what happens when the pawn moves and then the knight makes a move. Use BFS to find the shortest path to a vertex where both pieces are on the same square.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.