Complexity of Chess Domination Problems
From MaRDI portal
Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of packing and covering (05B40) Polyominoes (05B50) Recreational mathematics (00A08) Complexity of computation (including implicit computational complexity) (03D15) Computational aspects of satisfiability (68R07)
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 the problem is NP-complete for non-attacking queens on polyominoes and for non-attacking rooks on three-dimensional polycubes. We also analyze these problems on the set of convex polyominoes, for which we conjecture and give some evidence that these domination problems restricted to this subset of polyominoes might be NP-complete for both, queens and rooks. 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 minimal domination of queens and rooks on randomly generated polyominoes.
This page was built for publication: Complexity of Chess Domination Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6416821)
