# Dominating a Four Dimensional Chessboard with Rooks

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.

• 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. – M. Wind Jun 26 '15 at 15:23
• 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. – Mike Earnest Jun 26 '15 at 20:20
• 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. – M. Wind Jun 26 '15 at 20:58
• 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... – DVD Jul 4 '15 at 21:45

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)