论文标题
国际象棋统治问题的复杂性
Complexity of chess domination problems
论文作者
论文摘要
我们研究了在各个维度的多支着的多支着的攻击和非攻击的训练和皇后的攻击和皇后区的不同主导问题。我们的主要结果证明，对于非攻击的皇后和在尺寸三个及以上的多层上，最大独立的独立统治是NP完整的。我们还分析了多支粉和凸多个群机的这些问题，猜想了复杂性类别，并提供了用于研究的计算机工具。我们还计算了棋盘上经典女王统治问题的新值（正方形多摩尼亚）。对于我们的计算，我们将问题转化为整数线性编程实例。最后，使用这种计算实现和游戏引擎Godot，我们开发了一款视频游戏，以随机生成的多支着的多元在皇后区和Rooks的最低统治。
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.
