The Minimum Number Of Kings

A certain number of kings are placed on a $2014 \times 2014$ chessboard. A cell on a chessboard is called occupied if a king is placed on it. A cell is called vulnerable if it shares an edge with an occupied cell. Let $N$ be the minimum number of kings that must be placed on the chessboard to make sure all cells in the chessboard are vulnerable. Find the last three digits of $N.$

Details and assumptions

• In other words, there should exist no configuration with smaller than $N$ kings which makes all cells vulnerable. But, $N$ kings can be placed in such a way that all cells are vulnerable.
• A cell that is occupied need not be vulnerable.
• This problem is not original.