棋盘覆盖问题
The covering problem is that 1 king, 1 queen, 2 knights, 2 bishops, 2 rooks can threat the all 64 squares. Where should they be?
为了减少搜索空间,我们可以将皇后的可能位置限制在只有 10 个。
Getting the job done would require significant pruning. Our first idea was to remove symmetries. Accounting for orthogonal and diagonal symmetries left only ten distinct positions for the queen, shown in Figure
好的。我不明白这一点。
为什么女王的可能位置可以这样限制?
为什么可以考虑对称性来限制女王的位置?那么在上图中,皇后放在左下角和放在右下角是一样的吗?这是为什么?
最佳答案
如果将电路板旋转 90 度、180 度或 270 度,最终会遇到完全相同的问题。类似地,您将皇后移动到它的镜像位置(穿过对角线,或水平或垂直穿过棋盘的中间),结果结果与您没有移动时完全相同。
要理解对角对称性:
试着把皇后放在左下角,解决问题,然后把皇后放在右上角,解决问题。您会看到解决方案完全相同。
要了解旋转对称性:
尝试将皇后放在左下角,解决问题,然后移动到右下角。解决方案再次完全相同。
您可能希望使用较小的电路板(例如 4x4 或 6x6)来执行此操作,这样求解步骤就会更少,从而更容易掌握对称性。
关于algorithm - 为什么皇后在棋盘覆盖中只有 10 个独特位置?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10525024/