# Placing kings on a 6x6 board - who wins?

Two players alternate placing kings on a $$6\times6$$ chessboard, such that no two kings are allowed to attack each other (not even two kings placed by the same player). The last person who can place a king wins. Which player has a winning strategy?

Recall that, in chess, a king attacks the eight neighboring squares. (Incidentally, this problem is the same as placing $$2\times2$$ nonoverlapping boxes on a $$7\times7$$ grid.)

For an odd-sized board, the first player has a winning strategy: go in the middle and then mirror the other person's moves. For a $$2\times2$$ the first player wins trivially; for a $$4\times 4$$ the second player wins regardless of strategy (it will always end after four kings are placed). $$6\times6$$ is the first nontrivial case: while there can be at most nine kings on the board at once, the game could theoretically end after as few as four moves.

Ideally I'd like to know the answer for a general $$n\times n$$ board, but I figured I'd start small and work my way up. $$6\times6$$ proved trickier than I had anticipated.

• By the Sprague-Grundy theorem, we can also ask for the nim-value of these games. Jan 22 at 19:42
• Is the case $n=5$ trivial ? Jan 22 at 19:43
• @Peter Yes, first player wins by playing in the center then mirroring Jan 22 at 19:45
• The problem is equivalent to solving Node Kayles on the $6\times 6$ King's Graph Jan 22 at 19:55
• @ZubinMukerjee I admit, this is at least a simple strategy. Jan 22 at 20:02

I wrote some code to bash the nim values; a $$6\times 6$$ grid is a win for the first player with nim value $$1$$, by playing in any of the purple squares below:
If the first player plays in the middle of a $$3\times 3$$ quadrant, the following diagram shows their winning responses to any of the second player's replies:
• For the $3\times 3$ and $5\times 5$, I believe it's just the center. Certainly none of the other cells in the central $3\times 3$ region can work, since mirroring them produces a symmetric board and also forbids the center. Jan 24 at 18:59
Here’s Java code that computes the value of the game on the $$n\times n$$ board up to $$n=8$$. The results for $$n=6$$ coincide with those in RavenclawPrefect’s answer. For $$n=8$$, the first player loses whatever they play.