找到我可以在4*4棋盘中放置4个皇后的地方？

Question

我不是要求解决方案.我想要所有可能的展示位置.

Answer 1

有两种方法可以将4个皇后放在4x4棋盘上,这样任何一个皇后都不会攻击任何其他皇后:

_ ? _ _    _ _ ? _
_ _ _ ?    ? _ _ _
? _ _ _    _ _ _ ?
_ _ ? _    _ ? _ _

资源

算法

我不打算给你代码,但我可以告诉你算法应该如何工作.要找到解决方案,您可以使用带回溯的强力算法.

• 对于每一行,尝试在该行的第一个免费squre中放置一个女王,然后移动到下一行.
• 如果没有可用的正方形,则至少有一个女王在错误的地方.
• 返回上一行,将女王移动到下一个可用的方格.
• 重复,直到找到解决方案.

以下是该算法如何适用于4x4板:

? _ _ _
_ _ _ _
_ _ _ _
_ _ _ _

第二行的女王不能进入第一列或第二列因为它们都受到攻击,所以试试第三行:

? _ _ _
_ _ ? _
_ _ _ _
_ _ _ _

现在是第三行......没有空格可用.回溯并尝试第二行的新位置.

? _ _ _
_ _ _ ?
_ _ _ _
_ _ _ _

现在我们可以放置第三排女王:

? _ _ _
_ _ _ ?
_ ? _ _
_ _ _ _

第四排没有运气.我们已经尝试了第三行的每个位置,第二行,所以回溯到第一行:

_ ? _ _
_ _ _ _
_ _ _ _
_ _ _ _

等等...

祝好运!