ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > Python > 如何用 Python 解决 N 皇后问题？

如何用 Python 解决 N 皇后问题？

原创 Python 作者：mingtian66 时间：2024-11-13 10:29:31 0 删除 编辑

N 皇后问题要求在 N×NN×N 的棋盘上摆放 NN 个皇后，使得任意两个皇后之间不在同一行、同一列或同一对角线上。以下是使用 Python 递归和回溯方法来解决 N 皇后问题的代码：

def solve_n_queens(n):
    def is_valid(board, row, col):
        # 检查列和两个对角线是否有冲突
        for i in range(row):
            if board[i] == col or \
               board[i] - i == col - row or \
               board[i] + i == col + row:
                return False
        return True

    def solve(board, row):
        # 如果所有行都放置了皇后，记录解决方案
        if row == n:
            solution = []
            for i in range(n):
                row_solution = "." * board[i] + "Q" + "." * (n - board[i] - 1)
                solution.append(row_solution)
            solutions.append(solution)
            return

        # 尝试在当前行的每一列放置皇后
        for col in range(n):
            if is_valid(board, row, col):
                board[row] = col
                solve(board, row + 1)
                board[row] = -1  # 回溯

    solutions = []
    board = [-1] * n  # 初始化棋盘，每一行的值表示皇后所在列
    solve(board, 0)
    return solutions

# 测试
n = 4
solutions = solve_n_queens(n)
print(f"{n} 皇后的解法共有 {len(solutions)} 种：")
for solution in solutions:
    for row in solution:
        print(row)
    print()

代码说明：

    is_valid 函数：检查在 (row, col) 放置皇后是否安全。它检查之前所有行的皇后，判断是否有冲突。
        判断列冲突：board[i] == col
        判断左上到右下对角线冲突：board[i] - i == col - row
        判断右上到左下对角线冲突：board[i] + i == col + row

    solve 函数：递归地在每一行放置皇后。当放置完所有行的皇后时，将当前棋盘方案记录到 solutions 列表中。
        若放置皇后无冲突，将列位置保存到 board 中并递归到下一行。
        若递归返回时，则通过 board[row] = -1 回溯到上一步。

    主函数 solve_n_queens：初始化棋盘和解集 solutions，并调用递归函数 solve。

输出示例（4 皇后）：

4 皇后的解法共有 2 种：
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

这种方法的时间复杂度较高，但能有效地找到所有解。

来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/70040412/viewspace-3048575/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： java如何重新抛出异常并保留原始堆栈？
下一篇： 如何在 Python 中压缩和解压缩文件？
请登录后发表评论 登录
全部评论
mingtian66

注册时间：2024-08-07

  • 博文量
    589
  • 访问量
    603028

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593