在NxN的棋盘上放置N个象棋士的算法

Question

问题：在NxN的棋盘上放置N个主教，使得所有的方格都被至少一个主教占据或攻击。请提供一个有效的算法来解决这个问题。

解决方案：

- Cinnamon

---

我相信有人可以帮助你，你具体卡在哪里了？ - James McNellis

为什么不使用回溯呢？:-P - Vlad

嗯...皇后问题也有类似的情况，但你只需要检查当前放置的皇后是否在合法的方格上。但是对于象棋，你必须意识到整个算法中空方格的存在吗？这非常低效，不是吗？因为你需要在每次放置/移除象棋后重新"重绘"棋盘。 - Cinnamon

我认为你所提到的问题（http://en.wikipedia.org/wiki/Eight_queens_puzzle）规定皇后之间不允许互相攻击。而你所描述的象棋问题并没有这个限制。 - Mark Byers

Answer 1

_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
_ _ _ _ ♗ _ _ _ _
这是一个棋盘，每个黑点上有一个♗（象）棋子。

- Mark Byers

---

“回溯法”这个词表明OP想要得到所有可能的主教排列。 - Vlad

我知道解决方案。我需要算法方面的帮助。 - Cinnamon

@Cinnamon：该算法-1）选择任何一行或列。2）在此行或列的每个单元格中放置主教。但是说真的，如果这不是您想要的，如果您在问题中添加了更多细节，将有所帮助。解释：您想要什么，如何以及为什么应该使用回溯，您已尝试了什么，如果有代码，请提供，以及您在使其工作方面遇到的问题。 - Mark Byers

@Mark：它们必须位于中心。 - Potatoswatter

@Potatoswatter：好观点。我需要再加一步：3）如果你选择的行或列不起作用，回溯并尝试新的行/列。所以现在算法也包括了所要求的回溯。;-) - Mark Byers

Answer 2

这个问题有最小和最大解，但并不是那么简单。请查看BishopsProblem或更多

- stacker

---

我在C语言中找不到一个例子，只有理论。 - Cinnamon

@Cinnamon 这个（第二个贴子）可以用于主教移动。http://compsci.ca/v3/viewtopic.php?t=21497 - stacker

Answer 3

我假设您是在寻求一些优化，因为回溯算法就是它本身。

首先要注意的是，您可以将黑色和白色分开 - 您可以取 i + j = N 时的 B_i * W_j 之和。您还可以将对角线视为简单的网格（带有约束条件），这可能会使代码更紧凑，也更容易理解。另一个优化是注意到颜色并不一定重要-某些黑色的结果可以用于某些白色。找出何时发生以及何时不会发生。

希望这足够好-对于一些较小的N来说应该足够了。

- Larry

Answer 4

为什么要回溯？使用少量解决方案来获得证明。

即使是贪心算法也足够了：计算每个方格可到达的正方形数量。选择一个具有最大覆盖范围且不与先前选择的覆盖范围重叠的方格。重复此过程。

歧义会产生水平、垂直和中心侧面的变化。

N个主教只足以用一个主教到达每个方格。如果您选择了具有重叠覆盖范围的方格，则可到达的方格的最终总数将较低。嗯，也许您需要量化任何给定坏方格的降低程度。听起来可行。

对于如此庞大的问题空间，暴力回溯似乎并不可行。

- Potatoswatter