Given an NxM chessboard, you have a knight at some position and your opponent also has a knight, Find number of squares reachable to your knight in exactly K moves without being captured by opponent.There is no other piece other than 2 knights mentioned. You move first. Both players play optimally. Obvious solution would be to recursively try out each possibility for both knights but that would be too slow. Is there deterministic polynomial time solution ?

i guess the backtracking solution is the only way

You can store, for each number of moves, all squares your knight can occupy and all squares for the other one as well.

For example, before the first move, your knight can only be at it's initial position.

This can lead to an

O(K(NxM)^{2}) algorithm.