# Cover an unusual board with minimum chess rooks

This is an entry for the 17th Fortnightly Challenge.

On this unusual board, how many chess rooks minimum needed to attack all tiles, but they are not attacking each other ? Show us the formation.

Above are chess rooks attack pattern at blue tile.

To help them who can not edit picture use this numbering guide.

• How do the rooks move, if placed on the side of a cube (e.g. 6)? Oct 15, 2016 at 8:03
• @Sleafar : I will add a picture Oct 15, 2016 at 8:04
• Must the rooks attack all tiles including the tiles with rooks on (i.e. must each rook be defended by another rook)? Or not? Oct 15, 2016 at 8:18
• @RosieF : No, they are not attacking each other. Oct 15, 2016 at 8:21

Here is a solution with

$5$ rooks $(6, 14, 26, 38, 50)$:

I don't think less can be possible since

$4$ are required to attack the ends of the horizontals which together cannot attack all other cells. See how Yellow is required to attack $(2,3,31,34)$ in the above solution.

### Update

Here is code to search for solutions
- it is not generalised to any size, I just hard-coded the "rows" (horizontals, diagonals and anti-diagonals)
- it is zero based so all the numbers are one less that those shown in the question

N_CELLS = 57
ROWS = [{4,5,6,7,8,9,10,11},{19,20,21,22,23,24,25,26},{34,35,36,37,38,39,40,41},{49,50,51,52,53,54,55,56}, # Horizontals
{50,45},{42,35,52,46,30},{27,37,43,15,20,54,47,31},{32,0,48,5,39,12,44,16,22,56,28},{33,1,41,7,13,17,24,29},{9,18,26,2,14},{11,3}, # Diagonals
{0,4},{1,19,12,6,15},{34,8,2,13,16,21,27,30},{3,36,49,10,45,14,17,23,28,42,31},{32,38,43,46,18,51,25,29},{40,33,44,53,47},{48,55} # Anti-diagonals
]
ALL_CELLS = set(range(N_CELLS))

def makeAttackLookup():
res = []
for pos in range(N_CELLS):
a = set()
for r in ROWS:
if pos in r:
a |= r
res.append(set(a))
return res

ATTACK_LOOKUP = makeAttackLookup()

def iterSolutions(stop, curPos=[], curAttacks=set()):
if len(curAttacks) == N_CELLS:
yield curPos
elif len(curPos) < stop:
for pos in ALL_CELLS - curAttacks:
if not curPos or pos > curPos[-1]:
for solution in iterSolutions(stop, curPos + [pos], curAttacks | ATTACK_LOOKUP[pos]):
yield solution


Counting solutions (not collapsing into equivalence classes):

>>> c = 0
>>> for solution in iterSolutions(4): c+=1
...
>>> c
0
>>> for solution in iterSolutions(5): c+=1
...
>>> c
162

We can count how many there are up to symmetry by noting that

All solutions of $5$ must use exactly one of the top horizontal that is not an end: $\{6,7,8,9,10,11\}$
A solution using $6$ has a reflection in the vertical using $11$
Likewise for $7,10$ and $8,9$
There are $29$ solutions using $6$, $14$ using $7$ and $38$ using $8$
Total number of solutions up to symmetry is $29+14+38=81$ (half the number counted as expected by the fact there is only one reflection in the board).

I have a solution with 6 rooks:

• Nice try, but I think you can do it with less than 6 Oct 15, 2016 at 8:41
• @JamalSenjaya I'll have to try it later. Oct 15, 2016 at 8:49