寻找N-queens谜题递归算法的唯一解

Question

# -*- coding: utf-8 -*-


def puzzle(rows, cols):
    if rows == 0:
        return [[]]
    else:
        return new_queen(rows - 1, cols, puzzle(rows - 1, cols))


def new_queen(new_row, cols, plsd_queens):
    new_solutions = []
    for solution in plsd_queens:
        for new_col in range(cols):
            if test(new_row, new_col, solution):
                new_solutions.append(solution + [new_col])
    return new_solutions


def test(new_row, new_col, solution):
    for row in range(new_row):
        if solution[row] == new_col or solution[row] + row == new_col + new_row or\
                                solution[row] - row == new_col - new_row:
            return False
    return True

大家好！我怎样才能找到这个N皇后难题的递归算法的唯一解呢？它只找到所有的解决方案:在板载8x8上将有92个解决方案，但唯一的解决方案只有12个(其他解决方案是从这12个解决方案翻译和镜像的)

Answer 1

我认为这些很有用：link1 link2

为了获得最好的结果，你应该通过动态编程来设计你的算法，你可以在google Stackoverflow中找到它

您设置了一个数组，并将状态i保存在...这是n=8为item first提供的示例：

A= {5,1,8,4,2,7,3,6}{1}，.....

注意:每个解都可以通过对称性和rotation.So改变为8种状态，对于每个结果，你对称和旋转它们的解来检查它是否保存在你的数组中？