purist's blog

By purist, history, 5 weeks ago, In English,

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 ?

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

i guess the backtracking solution is the only way

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.