广度优先搜索示例

Question

我想知道下面的8个皇后问题的解决方案是否使用了广度优先搜索。它搜索所有可能的节点；但是，当没有任何地方可以合法放置女王时，前一个女王将被删除。如果没有，我想知道如何将其转换为使用广度优先搜索。

Answer 1

我要说的是，第八个女王问题的BFS解决方案的一般格式是获取解决方案的一些表示(比如从0到7的8个数字，表示女王在每一列中所在的行)，然后依次遍历可能的解决方案(从0000000到77777777)，注明每个可能的解决方案。

深度优先搜索和回溯，就像你使用的一样，更有效。有关这两种技术之间的比较，请参阅此article。

编辑:关于BFS的主题:有一些技巧可以让它更有效地解决这个问题。例如，如果您在第0行中放置了一个queen，那么您就知道不必在其他列中尝试该行中的queens。等。