32
$\begingroup$

Given an infinite (in all directions), $n$-dimensional chess board $\mathbb Z^n$, and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite number of moves?

To avoid trivial exceptions, assume the king starts a very large distance away from the nearest rook.

Rooks can change one coordinate to anything. King can change any set of coordinates by one.

And same problem with i) Bishops and ii) Queens, in place of rooks.

  • 0
    Is your infinite chessboard infinite in all directions, or does it have a corner?2012-06-08
  • 1
    4 isn't enough in 3d; I suspect that 9 is a legitimate minimum in 3d (and $3^{d-1}$ in arbitrary dimensions) because any 'safe' rook has to be covered by another 'unsafe' rook; certainly by counting arguments the obvious minimum scales as $3^d$, so the key questions are the constant of proportionality, and whether the lower bound is actually tight in any real sense.2012-06-08
  • 0
    This has an obvious connection to Conway's Angel problem (http://en.wikipedia.org/wiki/Angel_problem) and it might be worth having a look at some of those arguments.2012-06-08
  • 3
    Note that in 2 dimensions (infinite chessboard) a rook provides a 1-dimensional constraint. In more that 2 dimensions the rook provides a 1-dimensional constraint, which is not an (n-1)-dimensional constraint. You have to be more subtle - three rooks works in two dimensions.2012-06-08
  • 0
    I am also convinced that $3^{d-1}$ is correct. So I think the idea is to try and show that if the king is in a check situation with fewer than $3^{d-1}$ rooks then there is always a coordinate that can be changed by $1$ so that at least two coordinates of the king disagree with every rook.2012-06-09
  • 4
    It's not clear to me that a forced checkmate is even possible in 3 dimensions, unless you start with something that is nearly a cage. It seems to me that you can just barely keep up with the king when trying to form a wall to block off one direction of motion, but the king can race you in three directions at once.2012-06-09
  • 2
    Worse, I'm not even sure that you can block the king on *one* side, given that it usually takes two moves to move a rook to the desired position.2012-06-09
  • 0
    Not forgetting that in 3D and higher the king can fork two rooks placed in such a way that neither of the threatened rooks can move to support its brother. With some care, difficulties of this kind may be circumvented, but the answer is not at all clear.2012-06-09
  • 2
    Some of the comments here may be relevant: http://mathoverflow.net/questions/99124/rooks-in-three-dimensions-closed2012-06-09
  • 1
    @Hurkyl: You can capture the king in a square prison. You just need to create 4 L-shaped wedges at the 4 corners plus an additional 4 rooks to block the king off whenever he gets close to one of the edges.2012-06-10
  • 0
    Using this idea, you can use 13 rooks for each corner, plus 4 moving along each edge, plus one extra to start shrinking the prison to squash the king in, so 69 rooks will do it. That certainly isn't optimal though.2012-06-10
  • 0
    @George: Your strategy sounds good, but I'm pretty sure you don't need more than 7 at each corner. The extra shrinking piece also seems unnecessary, so I have a tentative upper bound of 44.2012-06-10
  • 0
    @ScottCarnahan: See my answer. Going through in detail used 96 rooks, but is a very wasteful strategy. Optimising the strategy, you can probably reduce this by quite a lot (maybe by 1/2).2012-06-10
  • 0
    So, 4-dimensional chess is still open. Is it possible to force checkmate with any number of rooks? I suspect not, but don't know how you would prove this.2012-06-10

3 Answers 3

27

In 3-dimensional chess, it is possible to force checkmate starting with a finite number of rooks. As this fact still appears to be open, I'll post a method of forcing checkmate with 96 rooks, even though it should be clear that this is not optimal. You can remove some of the rooks from the method I'll give below, but I am aiming for a simple explanation of the method rather than the fewest possible number of rooks.

First, we move all of the rooks far away in the $z$ direction, so that they cannot be threatened by the king. We also move each of the rooks so that they all have distinct $z$ coordinates. That way, they are free to move any number of steps in the $x$ and $y$ directions without blocking each other. The king will be in check whenever it has the same $(x,y)$-coordinate as one of the rooks. We can project onto the $(x,y)$-plane to reduce it to a 2-dimensional board. Looked at this way, each rook can move any number of places in the $x$ or $y$ direction (and can pass through each other, can pass through the king, and you can multiple rooks in the same $(x,y)$-square). The king is in check if it is on the same square as a rook.

First, I'll describing the following "blocking move" to stop the king passing a given horizontal (or vertical) line.

blocking move

In the position above, the right-most 3 rooks are stopping the king moving past the red line on the next move. Then, once the king moves, do the following. (i) If the king's $x$-coordinate does not change, do nothing. (ii) If the king's $x$-coordinate increases by one, move the left-most rook so that it is to the right of the other three. Then you are back in the same position, just moved along by one step. (iii) If the king's $x$-coordinate decreases by one step, do nothing. We are back in the same situation, except reflected (so, keep performing the same steps, but reflected in the $x$-direction on subsequent moves).

This way, we chase the king along the red line, but he can never cross it. Furthermore, if the king changes from going right to going left, we have a free move to do something elsewhere on the board. Actually, for this to work, if the king is in column $i$, we just need three rooks at positions $i-1,i,i+1$ on the row above the red line, and one more at any other position on the row. Next, if we have 4 rooks stationed somewhere on the given horizontal row, how many moves does it take to move them into the blocking position? The answer is 6. You first move one rook to have the same $x$-coordinate as the king (say, $x=i$). After the king moves, by reflection we can assume he keeps the same $x$-coordinate or moves one to the right. Then, move the next rook to position $i+2$. Then, after the next move, move a rook to position $i-2$ or $i+4$ in such a way that we have three rooks on the row, with one space between each of them, and the kings is in one of the 3 middle columns. Say, the rooks are at positions $j-2,j,j+2$ and the king is in column $j-1,j$ or $j+1$. If the king moves to column $j-1$ or $j+1$ we just move the 4th rook to this position and we have attained the blocking position. If the king moves to column $j$, we move the rook in position $j-2$ to position $j-1$ and, on the next move, we can move the 4th rook in to attain the blocking position. If the king moves to column $j+2$, we move the rook in column $j-2$ to $j+4$, then we are in the position above where there are rooks at positions $k-2,k,k+2$ and the king in position $k$, so it takes 2 more moves to attain the blocking position.

So, we just need to keep 4 rooks stationed along the row which we wish to block the king from crossing. Whenever he moves within 6 steps from this row, start moving the rooks into the blocking position, and he can never step into the given row.

Now, choose a large rectangle surrounding the king, and position 15 rooks in each corner as below.

rectangle

Also, position 4 rooks in arbitrary positions along each edge of the rectangle. So, that's $4\times15+4\times4=76$ rooks used so far. I puposefully left some of the board blank in the diagram above. The point is to not specify exactly how big the rectangle is. It doesn't matter, just so long as it is large enough to be able to move the 76 rooks into position before the black king can get within 6 steps of any of the edges of the rectangle.

Now, once we are in this position, then whenever the black king moves within one of the red rectangles, use the 4 rooks positioned along the adjacent edge to perform the blocking move as described above to stop the king crossing that edge. We can keep doing this, and imprison the black king within the big rectangle. Furthermore, we keep getting free moves to do something else whenever the king moves out of the red rectangles, or whenever he changes direction within a red rectangle. Also, if the king is in one of the inside corners of a red rectangle, there is already a rook in the corresponding position at the adjacent edge of the big rectangle, giving us a free move.

Now, suppose that we have an extra 20 rooks. During the free moves we get while chasing the king around the edge of the big square, we can move these to any position we like. With 20 rooks, we can position 16 of to the left of each of the 16 rooks near the right-hand corners of the big rectangle which have an empty square to their left. Also, position 4 rooks along the column one step to the left of the right-hand edge of the big rectangle. This way, we create a new rectangle one square smaller in the $x$-direction. If the king ever enters the right-hand red rectangle or one step to the left of this, we use the new 4 blocking rooks to stop him from reaching the right-hand edge of the new big rectangle. If he is already within the red rectangle, and stays there then, when we get a free move, we can move one of the new blocking rooks to the position one above or below the row in which the king is. Then we can bring the other 3 rooks in, blocking him out of this column. In this way, we create a new big rectangle one step smaller in the $x$-direction and with the king still trapped inside. Similarly, we can reduce the height of the big rectangle by 1. Repeat this, enclosing the king in ever smaller rectangles until, eventually, he gets trapped in the single square within a 3x3 rectangle surrounded by 8 rooks. Then bring one of the other rooks in to cover this square, which is checkmate.

  • 0
    Ah excellent! I was having the beginnings of this idea, but I was still stuck on the idea of building a continuous wall.2012-06-11
  • 0
    Refining this idea, I can get down to 40 rooks, and possibly fewer than that.2012-06-11
  • 0
    In the argument about using four rooks to block the king from passing a horizontal line, what stops the king from repeatedly moving (+1,0,+1)? The +1 on the x-direction forces the leftmost rook to move right to maintain the blocking formation. But the +1 on the z-direction allows the king to approach and eventually attack one of the rooks.2012-08-28
  • 0
    You could defeat this king strategy by using four more rooks to protect the four blocking rooks. The new rooks have the same y and z coordinate as the rook they protect, but a different x coordinate. Depending on where the king goes, the roles of the the "blocking" and "protecting" rooks will need to be swapped.2012-08-28
  • 0
    @Gareth: Sorry, I didn't see your response earlier. The idea is that first you move all the rooks far away in the z-direction. Far enough that the king can never attack them except after a lot of moves, and it will be checkmate before then anyway.2012-12-14
3

As the beginnings of an impossibility proof, let's consider the possibility of blocking off one direction of motion to the king in three dimensions. Consider the following game:

.............  ...........   .........    .......     .....      ...       K 

Each turn, you get to place one # on the top row, and then the king gets to move his K one space forward, either straight or diagonally, but cannot pass through a #. If the K reaches the back row, you lose. This game is actually winnable with this size grid or larger, but not with a smaller grid.

How does this compare to the chess game? Well, if we just consider one direction of motion, we can project from 3 dimensions down to two. If the king is not in the same plane as any of your rooks, then each of your rooks can block off a single square in the projected game.

Unfortunately, you can't really guarantee being able to place one rook per turn in the correct position (and don't forget in the real game, we are trying to block 3 directions of motion at once!) So now consider the same game, but the king gets to make two moves for every move you make.

I don't think you can win this version of the game.

Now, a better version of the game would be to let you place one # per turn anywhere, and the king gets two moves (or less, if he wants) per turn in any direction. I don't know if this game might be winnable; it's not quite the Conway Angel problem that was mentioned (jumping isn't allowed).

But again, you're trying to bound the king in three directions at once. So you're playing three games at once, and on your turn you get to place one piece on any of the three boards, but your opponent gets two moves (or less if he likes) on all boards at once. It seems... unlikely that this game is winnable.

So, in order to actually force a checkmate, you're going to have to do one of:

  • Take some advantage of the initial arrangement of your rooks
  • Find some way to make useful moves on two or three of the projected boards at once
  • Get your rooks in the same plane as the king frequently enough to be meaningful

It's not clear that this can be done.


Update: you don't need to win in 3 directions at once, just two. More precisely, consider a game on an infinite two-dimensional grid where you have pieces # and your opponent has a piece K. You and your opponent alternate turns, and the rules are:

  • You can move a # horizontally or vertically any distance.
  • You are allowed to move a # onto the K.
  • Your opponent can move one space in any of the 8 directions or remain still.
  • Your opponent is not allowed to end his turn on a #.

You win if your opponent has no legal moves. If you can win this game in N moves with M #'s, then you can force a checkmate as follows:

  • Imagine the above two-dimensional grid as a projection of the three-dimensional chessboard.
  • Move your rooks vertically 2M + N + lots more spaces away from the king, all with different vertical coordinates.
  • Play the above game, where the #'s are rooks and the K is the king.

If you can build walls quickly enough in just two dimensions, of course, that would give a winning strategy for the above game (given enough #'s): wall in the K, then move #'s to fill all of the interior squares.

1

Here is a rough sketch of how I think it goes. Clearly $3^{d-1}$ rooks can always create a checkmate situation in a finite number of moves.

Now suppose that we have $3^{d-1} - 1$ rooks and that the king is in check by one of them. We must show that the king can always escape.

Now there are at most $3^d - 1$ possible moves for the king in general. But the king is in check by one rook, so that actually the king has $3^d - 3$ possible moves (ignoring the position of the other rooks).

But the other $3^{d-1} - 2$ rooks can threaten at most $3$ adjacent squares of the king each (by the linear nature of the rooks attack) so that at most $3^d - 6$ of the $3^d - 3$ squares can be threatened. Thus there must exist squares adjacent to the king that are not threatened by any of the rooks.

  • 0
    Why does the king have $3^d-1$ possible moves?2012-06-09
  • 0
    You can add $\{0,\pm 1\}$ to any of the $d$ coordinates and except for adding $0$ to them all, we get the valid moves of a king.2012-06-09
  • 0
    Thanks. Unfortunately, I am still not convinced by the rest of your argument. Neither do I see the "clearly" (although it looks reasonable), nor do I agree that a rook can threaten at most 3 adjacent squares. (A rook can already threaten 4 squares in dimension two as long as it is covered by another rook. This does not pay off in dimension 2. But in higher dimension, a rook can threaten 2d squares, so the rook and the rook covering it threaten $d$ squares each.)2012-06-09
  • 0
    Ah, I think I ignored the case of the rooks being directly adjacent to the king. Back to the drawing board. My argument considers all cases where this doesn't happen.2012-06-09
  • 0
    A rook can actually threaten 3d-1 squares, in fact must threaten that many if it threatens more than 3.2013-09-20