BFS algorithm to determine the minimum number of steps for Knight Eliminate a moving pawn.
As the title says, I'm trying to intuitively understand this problem. Suppose we have a pawn and a knight in turn. The two pieces must move in turn, and both pieces have a starting position and assume that the board is large enough that the knight can eventually catch and eliminate the piece. I want to find the minimum of movement that the knight takes to eliminate the pawn.
I know we can use a BFS algorithm to find the shortest path between the Knight and a fixed point on the board, but I do not know how to proceed for a moving target. What happens if we make a BFS on each square of the column on which the pawn moves, then compare the number of moves made and check if any of these movement sequences results in the location of the pawn? But that does not always seem to work, because finding the minimum number of moves to reach the pawn might be less than the minimum number of moves required to catch the pawn, as the knight could "pick up" a bit until you reach the pawn. 39, he is in the right position to eliminate the pawn.