n皇后问题python代码

以下是n皇后问题的Python代码实现：

def solveNQueens(n):
    def DFS(queens, xy_dif, xy_sum):
        p = len(queens)
        if p==n:
            result.append(queens)
            return None
        for q in range(n):
            if q not in queens and p-q not in xy_dif and p+q not in xy_sum: 
                DFS(queens+[q], xy_dif+[p-q], xy_sum+[p+q])  
    result = []
    DFS([],[],[])
    return [ ["."*i + "Q" + "."*(n-i-1) for i in sol] for sol in result]

n = 4
print(solveNQueens(n))

相关问题

广度优先搜索n皇后问题python代码

以下是广度优先搜索解决n皇后问题的Python代码：

from queue import Queue

def is_valid(board, row, col):
    for i in range(row):
        if board[i] == col or \
        abs(board[i] - col) == abs(i - row):
            return False
    return True

def bfs(n):
    q = Queue()
    q.put([])
    while not q.empty():
        board = q.get()
        if len(board) == n:
            return board
        for i in range(n):
            if is_valid(board, len(board), i):
                q.put(board + [i])

def print_board(board):
    for row in board:
        line = ""
        for col in range(len(board)):
            if col == row:
                line += "Q "
            else:
                line += ". "
        print(line)

n = 8
board = bfs(n)
print_board(board)

该代码使用队列实现广度优先搜索算法，每次取出一个棋盘，检查其是否合法，如果合法就将其所有可能的下一步棋盘加入队列中。当棋盘长度为n时，返回该棋盘。最后打印出解决方案。

回溯法求n皇后问题 python代码

下面是使用回溯法求解N皇后问题的Python代码：

def is_valid(board, row, col):
    """
    检查在(row, col)位置放置皇后是否合法
    """
    n = len(board)
    # 检查列是否有冲突
    for i in range(n):
        if board[i][col] == 1:
            return False
    # 检查右上方是否有冲突
    i = row - 1
    j = col + 1
    while i >= 0 and j < n:
        if board[i][j] == 1:
            return False
        i -= 1
        j += 1
    # 检查左上方是否有冲突
    i = row - 1
    j = col - 1
    while i >= 0 and j >= 0:
        if board[i][j] == 1:
            return False
        i -= 1
        j -= 1
    # 该位置可以放置皇后
    return True


def solve_n_queens(n):
    """
    解决N皇后问题
    """
    board = [[0] * n for _ in range(n)]
    res = []
    def backtrack(board, row):
        # 找到一个可行解
        if row == n:
            res.append(["".join(["Q" if c == 1 else "." for c in r]) for r in board])
            return
        for col in range(n):
            if is_valid(board, row, col):
                # 在当前位置放置皇后
                board[row][col] = 1
                # 继续搜索下一行
                backtrack(board, row+1)
                # 撤销当前选择
                board[row][col] = 0
    backtrack(board, 0)
    return res

使用示例：

res = solve_n_queens(4)
for solution in res:
    print(solution)

输出结果：

[".Q..", "...Q", "Q...", "..Q."]
["..Q.", "Q...", "...Q", ".Q.."]