First, consider the graph where nodes correspond to squares on the grid, and there is an edge between nodes whose squares are a knight's move away. Note that it can easily be shown that this graph is bipartite: simply color the grid like a chess board and realize that any two squares a knight's move away are different colors. Now, we are looking for the size of the largest set of nodes such that no two nodes have an edge between them.

It turns out that this is the size of the maximum independent set, which is equal to the number of nodes minus the size of the minimum vertex cover. And, size of minimum vertex cover is equal to the size of maximum matching in bipartite graphs, by König's theorem. So, finding the size of the maximum bipartite matching gives the answer.

Close enough.

http://community.topcoder.com/stat?c=problem_statement&pm=6070

:)