python - 皇后区拼图广度优先

Question

我被告知要编写一个程序，使用广度优先搜索来解决八皇后之谜。这是我到目前为止所得到的：

def n_queens(n, width):
if n == 0:
    return [[]
else:
    return add_queen(n-1, width, n_queens(n-1, width))


def add_queen(new_row, width, previous_solutions):
solutions = []
for sol in previous_solutions:
    for new_col in range(width):
        if safe_queen(new_row, new_col, sol):
            solutions.append(sol + [new_col])
return solutions


def safe_queen(new_row, new_col, sol):
for row in range(new_row):
    if (sol[row] == new_col or                  
        sol[row] + row == new_col + new_row or
        sol[row] - row == new_col - new_row):
            return 0
return 1

for sol in n_queens(8, 8):
print sol

有什么办法可以改善这一点吗？

Answer 1

同意以前的条目。上面描述的算法是“深度优先”搜索而不是“广度优先”搜索，并且对于这类问题更有效。

Answer 2

我不认为 BFS 完全符合我对这个问题的推理方式。相反，专注于递归生成可能的展示位置。对于每个放置的皇后，在下一行中只有一定数量的可能放置不能被攻击。“放置”一个皇后并在每个位置上递归，并在您放置皇后总数时终止。希望您会认识到混入一些递归调用的 for 循环似乎是一个不错的主意。还记得在递归返回时“拾取”您放置的皇后。