12
$\begingroup$

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.

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

2 Answers 2

11
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ The next step would be to see if there's a human-viable strategy hidden here. (Perhaps even a generalizable one.) $\endgroup$ Jan 23 at 21:08
  • $\begingroup$ It's not very elegant, but I think it's pretty human-viable to memorize at least one winning reply to all of P2's first moves in the diagram above and then just brute force whatever's left after they respond (by that point there are already four kings on the board so the game tree should be fairly small). Note that by symmetry the memorization task only involves 15 things rather than 27, and 8 of those 15 can be countered by a single response. I see some helpful mnemonics - eg if P2 plays on the far edge of the L left over by your first move, it's always a winning move to mirror them. $\endgroup$ Jan 23 at 21:43
  • 1
    $\begingroup$ Another reasonable question would be: for odd sized boards, we know that the center is a winning move…. but what other winning first moves are there? $\endgroup$ Jan 24 at 18:28
  • $\begingroup$ 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. $\endgroup$ Jan 24 at 18:59
5
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .