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

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.

• 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. – Apass.Jack Mar 31 at 15:33
• 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? – D.W. Mar 31 at 18:48
• @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. – jd94 Mar 31 at 19:46
• 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. – D.W. Mar 31 at 19:52

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.