Abstract
We study different domination problems of attacking and non-attacking rooks and queens on polyominoes and polycubes of all dimensions. Our main result proves that maximum independent domination is NP-complete for non-attacking queens and for non-attacking rooks on polycubes of dimension three and higher. We also analyze these problems for polyominoes and convex polyominoes, conjecture the complexity classes, and provide a computer tool for investigation. We have also computed new values for classical queen domination problems on chessboards (square polyominoes). For our computations, we have translated the problem into an integer linear programming instance. Finally, using this computational implementation and the game engine Godot, we have developed a video game of minimum domination of queens and rooks on randomly generated polyominoes.
Funding Information
  • Fonds de Recherche du Quebec- Nature et Technologies (270527)
  • HORIZON EUROPE Marie Sklodowska-Curie Actions (754462)
  • Fonds Wetenschappelijk Onderzoek (EOS3088945)
  • Bundesministerium für Forschung, Technologie und Raumfahrt (ScaDS.AI)
  • Max Planck Institute for Mathematics in the Sciences

This publication has 20 references indexed in Scilit: