Python程序：检查是否能在N皇后问题中获得解决方案

更多Python相关文章，请阅读：Python 教程

N皇后问题是什么？

N皇后问题是指在一个 N×N 的棋盘上放置 N 个皇后，使得皇后彼此之间不能相互攻击，即一个皇后不能与任何其他皇后处于同一行、同一列和同一斜线上。

例如，在一个 8×8 的棋盘上放置 8 个皇后，使得每个皇后互不攻击。

如何解决N皇后问题？

用回溯法可以很好的解决这个问题。回溯法，也称试探法，是一种基于搜索的算法，用来在一定的约束条件下，通过逐步建立可行解向前搜索，当搜索到某一步不能达到更好的状态时，就返回之前的步骤并进行其他的路径搜索。

在N皇后问题中，我们可以用一个一维数组arr，arr[i]表示第i行皇后所在的列数。通过枚举所有的可能的列数，我们可以判断当前摆放的皇后是否合法，如果是，我们就将arr中当前元素进行遍历并从下一行再次开始处理，如果不是，则继续枚举下一列。

如何检查是否能获得解决方案？

下面是Python实现代码。在这个代码中，我们先用一个数组记录下了N皇后问题的所有解决方案（即arr），然后我们根据这个数组，遍历了所有的解决方案，找到了最终的成功方案。

def printBoard(arr):
    board = [['.' for i in range(len(arr))] for j in range(len(arr))]
    for i in range(len(arr)):
        board[i][arr[i]] = 'Q'
    for i in range(len(board)):
        board[i] = ''.join(board[i])
    return board

def solveNQueens(n):
    def dfs(depth, cur_state, ans):
        if depth == n:
            ans.append(cur_state)
            return
        for i in range(n):
            if i not in col and depth + i not in diagonal and depth - i not in anti_diagonal:
                col.add(i)
                diagonal.add(depth + i)
                anti_diagonal.add(depth - i)
                dfs(depth + 1, cur_state + [i], ans)
                col.remove(i)
                diagonal.remove(depth + i)
                anti_diagonal.remove(depth - i)

    col, diagonal, anti_diagonal, ans = set(), set(), set(), []
    dfs(0, [], ans)
    res = []
    for solution in ans:
        res.append(printBoard(solution))
    return res

n = 4
res = solveNQueens(n)
if not res:
    print("在{0}x{0}的棋盘中，无法放置{1}个皇后.".format(n, n))
else:
    print("在{0}x{0}的棋盘中，可以放置{1}个皇后的方案如下:".format(n, n))
    for i in range(len(res)):
        print("\n方案{0}:".format(i+1))
        for j in range(len(res[i])):
            print(res[i][j])

在上述代码中，我们使用了回溯法求解N皇后问题，并且根据这个代码输出了所有可能的解决方案。在这个输出中，如果没有找到解决方案，则会输出”No solution exists for the given N”.是在{N}x{N}的棋盘中无法放置N个皇后。