36
$\begingroup$

Given is an infinite 3-dim chess board and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite number of moves?

(In 3-dimensional chess rooks move in straight lines, entering each cube through a face and departing through the opposite face. Kings can move to any cube which shares a face, edge, or corner with the cube that the king starts in. See Wikipedia).

Update: Comments (below the line) give interesting information on this problem including a connection to Conway's angel problem with 2-angel (Zare) and interesting comments towards positive answer and connection with "kinggo" (Elkies). Also a link to an identical SE question is provided MSE Question 155777 (Snyder).

Improve this question
$\endgroup$
36
  • 27
    $\begingroup$ It's closed because there seem to be too many trigger-happy people on the local `closing committee'. This is a bit worrying. $\endgroup$
    – Nikita Sidorov
    Jun 8, 2012 at 18:17
  • 16
    $\begingroup$ META: tea.mathoverflow.net/discussion/1384/rooksinthreedimensions $\endgroup$
    – Will Jagy
    Jun 8, 2012 at 20:53
  • 18
    $\begingroup$ In three dimensions a finite number of rooks should suffice by projection to "Kinggo": the King starts in the middle of an $N \times N$ square, then after each King move the opponent gets to claim a square at the edge of the board; the King is known to lose by force ($N=33$ suffices for Kinggo, maybe here we'll use something like $N=45$ to accommodate the initial setup). The king is then restricted to an $N \times N \times \infty$ box, so $N^2$ rooks suffice to force checkmate, and actually $5N$ will do. So $200$ rooks win in ${\bf Z}^3$. In ${\bf Z}^4$ and above, I don't know. $\endgroup$
    – Noam D. Elkies
    Jun 9, 2012 at 0:57
  • 25
    $\begingroup$ Will Jagy, are you able to direct me to the part of the FAQ that stipulates that it is considered undesirable to post a MathOverflow question before leaving work, and then come back the next morning to deal with replies? I ask because some might be unaware with this rule, and, finding that it is in concord with their personal schedules, feel a certain compulsion to do so. $\endgroup$
    – James Cranch
    Jun 9, 2012 at 1:04
  • 15
    $\begingroup$ And to be clear, I don't think "asked on rec.puzzles in 1994" is a good enough reason to close a question. If you provided a link, maybe; but just a statement like that and then voting to close is not really becoming of a high-rep user such as yourself. And I don't think the policy here should be to close these questions, then have a high-rep user repost it with more details. Shouldn't we encourage the OP to alter the question instead? $\endgroup$
    – Steve D
    Jun 9, 2012 at 20:45

2 Answers 2

Reset to default
18
$\begingroup$

As far as I know, it is still open whether or not there is any finite number of rooks which can force checkmate. However, this is possible. I answered the question over at math.stackexchange describing a strategy which forces checkmate with 96 rooks. This is certainly not optimal. The strategy I describe is very wasteful, keeping some rooks in place even when they are not actually needed, so it can be improved at the expense of becoming more difficult to describe.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @George Lowther: Looked at your nice answer on math.stackexchange. Shouldn't it generalize to $n$ dimensions? As per your answer, the rooks should be placed far away from the king along the $n$-th coordinate. As per your answer, the initial steps would still allow the king to roam freely along the $n$-th coordinate but aim to restrict its movement projected to the first $n-1$ coordinates. Each rook, far away along the $n$-th coordinate, guards one square having the same $n$-th coordinate as the king. $\endgroup$
    – user22202
    Jun 11, 2012 at 5:02
  • $\begingroup$ As in your answer, at the penultimate step, the king should be trapped in the middle of a $3^{n-1}$ cube, but be able to move freely along the $n$-th coordinate. (Each position on the boundary of this cube being guarded by a rook far away along the $n$-th coordinate.)Then place a rook far away along the $n$-th coordinate but having the same first $n-1$ coordinates as the king, to give checkmate. The initial number of rooks to begin with probably depends on $n$, no idea how exactly though. $\endgroup$
    – user22202
    Jun 11, 2012 at 5:03
  • 6
    $\begingroup$ I am confused. In the first sentence, you say it's still open whether or not any finite number of rooks can force checkmate. In the second sentence, you say that 96 rooks can force checkmate. I suspect that it's the first sentence which I am parsing incorrectly, but in that case I have no idea what it is supposed to mean. $\endgroup$
    – bof
    Dec 18, 2014 at 19:34
7
$\begingroup$

The following is for a finite board (the question actually assumes an infinite board).

For an $N\times N \times N$ board, wouldn't $2N$ rooks suffice? The idea comes from adapting the checkmate with two rooks for the two dimensional case in which the two rooks alternate rows and force the king to the last rank.

For the three dimensional case, for each $y$ with $1\leq y \leq N$, place one rook at $(1,y,k)$ and another at $(2,y,k+1)$. Then, for $y$ going from $1$ to $N$, move the rook at $(1,y,k)$ to the square $(1,y,k+2)$. Again, for $y$ going from $1$ to $N$, move the rook at $(2,y,k+1)$ to $(2,y,k+3)$. Each for loop over $y$ involves moving, alternately, the rooks with $x$ coordinate $1$ by increasing their $z$ coordinate by $2$ units, or the rooks with $x$ coordinate $2$ by increasing their $z$ coordinate by $2$ units. We alternate, so that a for loop in which the rooks with $x$ coordinate $1$ are moved is followed by a for loop in which the rooks with $x$ coordinate $2$ are moved, and vice versa. Eventually, either the rooks with $x$ coordinate $1$ or the rooks with $x$ coordinate $2$ will have $z$ coordinate $N$.

The effect of this is that a subset of the squares guarded by the rooks form a "floor" of two layers that keeps moving upward. So if the black king is between this "floor" and the top of the $N\times N\times N$ cube, it gets pushed to the top face. The "floor" must be moved upward in such a way that it never becomes disconnected, so that the black king can never escape to beneath the "floor" through some gap.

For an infinite board, @Noam Elkies has already mentioned $5N$, so the following is not an improvement: the "ceiling" (and the other walls of the $N\times N \times N$ cube) can be formed by placing $N$ more rooks at $(N,y,N)$, for each $y$ with $1\leq y\leq N$, and $N-1$ more rooks at $(x,1,N)$, for each $x$ with $1 \leq x \leq N-1$, and $N-1$ more rooks at $(x,N,N)$ for each $x$ with $1 \leq x \leq N-1$.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Actually, as long as $N$ is large enough to get started, 12 rooks should suffice. Use 4 rooks to perform the "blocking move" described in my math.SE post, with another 4 rooks protecting them. This traps the king in one half of the board - i.e. to one side of a plane containing these 8 rooks. Then, move the other 4 rooks in to push the king one step away from this plane, and move 4 of the original 8 rooks across to protect them. Repeat until the king gets pushed off the edge of the board. $\endgroup$
    – George Lowther
    Jun 11, 2012 at 1:04
  • $\begingroup$ The question is for an infinite board though, so there is no "last rank". $\endgroup$
    – George Lowther
    Jun 11, 2012 at 1:08
  • $\begingroup$ @George Lowther: Right! An infinite board. Corrected the answer, thank you very much! $\endgroup$
    – user22202
    Jun 11, 2012 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.