9
$\begingroup$

There is a family of chess problems where you try to dominate a board with as few copies of a given piece as possible. The chessboard is dominated if every square either contains a piece, or is attacked by one.

For example, to dominate a usual chessboard with $8$ rooks, simply place a rook on every square of a diagonal. You can easily verify this is optimal, that is, no $7$ rooks can dominate a chessboard. This result easily extends to an $n\times n$ board, for any $n$.

You can also ask about rook domination in three dimensions, where rooks can slide left/right, back/front, or up/down. This problem is harder, but there is a nice solution: $\lceil n^2/2\rceil$ rooks are necessary and sufficient to dominate an $n\times n\times n$ board. See here for a proof.

My question is about the four dimensional case. Here, there are four axes, and rooks can slide along any axis. Specifically,

How many rooks does it take to dominate a $4\times4\times4\times4$ board?

I was wondering if anyone had studied this problem before, or had any good ideas of an attack.

I know that $32$ rooks are sufficient, while $22$ rooks are insufficient. I've filled pages trying to succeed with $31$ rooks, to no avail. If your curious, the optimal number for a 2 x 2 x 2 x 2 board is 4 rooks, and for a 3 x 3 x 3 x 3 board is 9 rooks.

$\endgroup$
  • $\begingroup$ I would probably write a simple computer programme. Given the positions of the rooks, it would check for each of the $256$ squares whether it is controlled by $0$, $1$ or multiple rooks. This helps to avoid mistakes and it might indicate which rook positions can be improved. $\endgroup$ – M. Wind Jun 26 '15 at 15:23
  • $\begingroup$ This is a good idea, but in order to check whether $31$ rooks is enough, the program would need to check all $\binom{256}{31}\approx 2^{132}$ possible placements of $31$ rooks. Even using the board's symmetry check $(4^!)^5$ cases at a time, this is too big to brute force. $\endgroup$ – Mike Earnest Jun 26 '15 at 20:20
  • $\begingroup$ Sure ! But I don't mean an intelligent programme which optimizes the configuration. Just a very basic programme where you, the user, enter a configuration and the computer tells you the result. You can then move one rook to another square and see if it improves the domination or not. $\endgroup$ – M. Wind Jun 26 '15 at 20:58
  • $\begingroup$ The terms in the determinant expansion give the rook positions for the $n$ by $n$ matrix. So, possibly one needs to make sense of a 4D determinant to solve the problem... $\endgroup$ – DVD Jul 4 '15 at 21:45
2
$\begingroup$

I asked this question on Math Overflow as well, and got an answer which may be of interest. One of the answers provides a $24$ rook solution, and the other provides a source saying that $24$ is the minimum number required.

Viewing the hypercube as the set of points $(x,y,z,t)$, with $0\le x,y,z,t \le 3$ all integers, below is the locations of the rooks in a $24$ rook solution.

(0, 0, 0, 0)   (0, 0, 0, 1)   (0, 1, 1, 2)   (0, 2, 2, 3)   (0, 2, 3, 3)   (0, 3, 1, 2)
(1, 0, 1, 3)   (1, 1, 2, 0)   (1, 1, 3, 1)   (1, 2, 0, 2)   (1, 3, 2, 1)   (1, 3, 3, 0)
(2, 0, 2, 2)   (2, 0, 3, 2)   (2, 1, 0, 3)   (2, 2, 1, 0)   (2, 2, 1, 1)   (2, 3, 0, 3)
(3, 0, 1, 3)   (3, 1, 2, 1)   (3, 1, 3, 0)   (3, 2, 0, 2)   (3, 3, 2, 0)   (3, 3, 3, 1)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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