This is a problem from spoj
A and B are playing a very interesting variant of the ancient Indian game 'shatranj(also known as chess)' on a 'maidaan'(chessboard) n×n in size.
They take turns to put game pieces called 'ghoda'(knight) so that no two 'ghodas'(knights) could threat each other.
A 'ghoda' located in square (a,b) can threat squares (a+1,b+2),(a-1,b+2),(a+1,b-2),(a-1,b-2),(a+2,b-1),(a+2,b+1),(a-2,b-1),(a-2,b+1).
The player who can't put a new 'ghoda' during his move loses. Find out which player wins considering that both players play optimally well and A starts.
I cannot use brute force as n is very large, Is there an O(n) or O(1) algorithm for this problem?
Hint: consider a strategy when one player answers the moves of his opponent by central symmetry. For which $n$ does it work for the second player? When it doesn't work for the second player, can the first one use the strategy instead?