38
$\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.

$\endgroup$
14
  • 1
    $\begingroup$ 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. $\endgroup$
    – Steven Stadnicki
    Commented Jun 8, 2012 at 20:59
  • 4
    $\begingroup$ 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. $\endgroup$
    – Mark Bennet
    Commented Jun 8, 2012 at 21:30
  • 4
    $\begingroup$ 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. $\endgroup$
    – user14972
    Commented Jun 9, 2012 at 11:55
  • 2
    $\begingroup$ 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. $\endgroup$
    – user14972
    Commented Jun 9, 2012 at 12:42
  • 2
    $\begingroup$ Some of the comments here may be relevant: mathoverflow.net/questions/99124/… $\endgroup$
    – TROLLHUNTER
    Commented Jun 9, 2012 at 14:35

3 Answers 3

Reset to default
32
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Ah excellent! I was having the beginnings of this idea, but I was still stuck on the idea of building a continuous wall. $\endgroup$
    – user14972
    Commented Jun 11, 2012 at 6:56
  • 1
    $\begingroup$ Refining this idea, I can get down to 40 rooks, and possibly fewer than that. $\endgroup$
    – George Lowther
    Commented Jun 11, 2012 at 10:16
  • $\begingroup$ 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. $\endgroup$
    – Gareth Rees
    Commented Aug 28, 2012 at 22:28
  • $\begingroup$ 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. $\endgroup$
    – Gareth Rees
    Commented Aug 28, 2012 at 22:34
  • 1
    $\begingroup$ @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. $\endgroup$
    – George Lowther
    Commented Dec 14, 2012 at 21:33
4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Why does the king have $3^d-1$ possible moves? $\endgroup$
    – Phira
    Commented Jun 9, 2012 at 11:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – fretty
    Commented Jun 9, 2012 at 11:27
  • $\begingroup$ 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.) $\endgroup$
    – Phira
    Commented Jun 9, 2012 at 11:35
  • $\begingroup$ 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. $\endgroup$
    – fretty
    Commented Jun 9, 2012 at 11:40
  • $\begingroup$ A rook can actually threaten 3d-1 squares, in fact must threaten that many if it threatens more than 3. $\endgroup$
    – jwg
    Commented Sep 20, 2013 at 15:51

You must log in to answer this question.

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