Abstract
How many chess rooks or queens does it take to guard all squares of a given polyomino, the union of square tiles from a square grid? This question is a version of the art gallery problem in which the guards can “see” whichever squares the rook or queen attacks. We show that $$\lfloor {\frac{n}{2}} \rfloor $$⌊n2⌋ rooks or $$\lfloor {\frac{n}{3}} \rfloor $$⌊n3⌋ queens are sufficient and sometimes necessary to guard a polyomino withntiles. We then prove that finding the minimum number of rooks or queens needed to guard a polyomino is NP-hard. These results also apply tod-dimensional rooks and queens ond-dimensional polycubes. Finally, we use bipartite matching theorems to describe sets of non-attacking rooks on polyominoes.
Funding Information
  • Division of Mathematical Sciences (DMS 1802914)
  • Projekt DEAL

This publication has 24 references indexed in Scilit: