Placing kings on a 6x6 board - who wins?

626 Views Asked by At

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.

2

There are 2 best solutions below

4
On BEST ANSWER

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:

                              enter image description here

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:

enter image description here

0
On

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.