Consider an NxN chess board. What is the minimum number of Rooks (Castles) that it would take to dominate the board? Now consider an NxNxN hyper chess board. What is the minimum number of hyper rooks that it would take to dominate the board (NB Hyper Rooks can move up, down and across - ie in all 3 dimensions)?
The following image contains the answer as it was sent to me by Rich. I can't get the formulae to show in the comment section, so this is my best solution. So consider this a spoiler alert!
I assume that by "dominate" you mean cover every square? It definitely takes N rooks to dominate an NxN chess board. For 2x2x2 it only takes 2. For 3x3x3, it only takes 3. However, I think it takes more than 4 for a 4x4x4 board. The other two worked with guys just along the diagonal of the cube.
ReplyDeleteScratch that, can't do 3x3x3 with just 3 guys...
ReplyDeleteI think I can do it for (the NxNxN board):
ReplyDeleteN=1, 1 rook
N=2, 2 rooks
N=3, 5 rooks
N=4, 10 rooks
N=5, 17?
Anyway, that last one is a guess with (N-1)^2+1 rooks, based on the pattern from the first three...
Abe,
ReplyDeleteI think you can do it with less. I don't know if this will come out easily in words or not, but here goes.
A 1x1x1 and 2x2x2 cube are the exception to what I'm thinking and I agree that the N=1, is 1 and N=2 is 2.
With every other cube, try this.
Top layer: put a rook on the NorthWest (NW) and SouthEast (SE) corner.
Bottom layer: put a rook alternate corners, NE and SW.
This covers the outside rim of the top and bottom layers and also covers the corners of every other layer.
1 - - - -
! o o o !
! o o o !
! o o o !
! - - - 2 on the top
- - - - 3
! o o o !
! o o o !
! o o o !
4 - - - - on the bottom
Now you are left with the middle portion of the inner layers.
First Inner Layer: start one in and one over in the NW corner with rook #5 and place one diagonally on that same layer until you reach one block from the SE corner, (it has already been covered by the rook on either the top or bottom).
So if you are working with a 5x5x5, you'll place two on the top, two on the bottom, and now you're left with a 3x3 grid on layers 2,3,4.
Place rooks like this:
o o o o o
o 5 o o o
o o 6 o o
o o o 7 o
o o o o o on the 2nd layer down.
o o o o o
o o o 8 o
o 9 o o o
o o 10 o o
o o o o o on the 3rd layer down.
o o o o o
o o 11 o o
o o o 12 o
o 13 o o o
o o o o o on the 4th layer down.
The middle layers are kind of a Sudoku approach. Each layer must have a rook on each row and column with no doubles. This covers all of the squares on each of the inner layers but not the corners. The corners are covered by the top and bottom layers.
Hence, every NxNxN (3 or greater) will have 4 total rooks on the top and bottom layers with (N-2)^2 rooks in the middle layers.
5x5x5: 4 rooks for the top and bottom plus (5-2)^2. 4+(3^2), 4+9=13.
6x6x6: 4+4^2=20
So I think the formula is:
4+(n-2)^2
Yes, I agree. Good work.
ReplyDeleteIndeed, good work pilot, however there is a better solution, forget about the 4 rooks in corners and consider the 2x2x2 solution and you will get the minimum! (NB I've emailed the answers to Mike, but is his prerogative as to when they are posted. Having only recently emailed them, is my fault if they are late!)
ReplyDeleteHey Rich, I don't think I can get your answer into the comments section. I was thinking I would take a picture of it and insert it into the post itself. It may be my only way to get the formulas you used...
ReplyDelete