11
$\begingroup$

This is an entry for the 17th Fortnightly Challenge.


Unusual board
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.

chess rook attack pattern 1 chess rook attack pattern 2
Above are chess rooks attack pattern at blue tile.

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

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

Here is a solution with

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

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).

$\endgroup$
3
$\begingroup$

I have a solution with 6 rooks:

solution

$\endgroup$
  • $\begingroup$ Nice try, but I think you can do it with less than 6 $\endgroup$ – Jamal Senjaya Oct 15 '16 at 8:41
  • $\begingroup$ @JamalSenjaya I'll have to try it later. $\endgroup$ – Sleafar Oct 15 '16 at 8:49

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.