在棋盘覆盖问题
覆盖问题是 1 个国王、1 个皇后、2 个骑士、2 个主教、2 个白车可以威胁所有 64 个方格。他们应该在哪里？
为了减少搜索空间，我们可以将女王的可能位置限制为只有 10 个。
完成工作需要大量修剪。我们的第一个想法是消除对称性。考虑到正交和对角对称，女王只剩下十个不同的位置，如图所示
行。我不明白这一点。
为什么女王的可能名额可以这样限制？
为什么可以考虑对称性来限制女王的位置？那么上图中，queen放在左下角和放在右下角是一样的吗？这是为什么？
问问题
179 次
2 回答
4
如果将电路板旋转 90、180 或 270 度，最终会遇到完全相同的问题。同样，您将皇后移动到它的镜像位置（穿过对角线，或水平或垂直穿过棋盘的中间），结果证明与您没有移动时完全相同。
要理解对角对称：
试着把皇后放在左下角，解决问题，然后把皇后放在右上角，解决问题。您将看到解决方案完全相同。
要了解旋转对称性：
尝试将皇后放在左下角，解决问题，然后移动到右下角。解决方案再次完全相同。
您可能希望使用较小的板（例如 4x4 或 6x6）来执行此操作，以便解决方案步骤更少，从而更容易掌握对称性。
于 2012-05-09T22:33:58.343 回答
2
一般来说，对称只对放置的第一块有效。一旦一块棋子放在棋盘上，您就会失去部分或全部对称性：棋盘在镜像或旋转时看起来不再一样。
您发布的问题似乎假设皇后是放置的第一块。对于特定的问题，这是有道理的，因为皇后可以比其他任何棋子覆盖更多的棋盘，因此可以减少放置剩余棋子所需的工作。但是，无论您首先放置什么棋子，对称方面都是相似的：只有第一个棋子可以利用整个棋盘的对称性。
请注意，一旦放置了第一块，可能仍然存在一些残余对称性，这可以节省额外的时间。例如，如果第一块沿对角线放置，您仍然可以沿该对角线镜像。然而，这种残余对称性将需要更复杂（且容易出错）的代码来利用......
于 2012-05-09T23:31:55.967 回答