Python实现八皇后问题的回溯算法详解

远山来客

发布时间：2026-10-13| 6人浏览过

原创

本文详细介绍使用Python解决八皇后问题的回溯算法。通过定义冲突检测函数判断皇后位置是否合法，并利用递归生成所有可能的摆放方案。文章包含完整代码示例及运行结果分析，帮助开发者理解递归调用与状态更新机制，适用于Python数据结构与算法学习。

本文通过具体实例展示如何使用Python解决经典的八皇后问题，供读者参考学习。

八皇后问题源于国际象棋规则：在8×8的棋盘上放置八个皇后，确保它们互不攻击。这意味着任意两个皇后不能处于同一行、同一列或同一条对角线上。该问题可推广至n皇后问题，即棋盘大小为n×n，皇后数量为n。当且仅当n=1或n≥3时，该问题存在解。

这是一个典型的回溯算法应用场景，我们可以将解决过程分解为以下几个步骤：

首先，需要设计一种冲突检测机制，确保新放置的皇后不会与已有皇后产生攻击关系，即不能处于相邻位置或同一对角线上。

其次，利用回溯法求解。具体实现为函数的递归调用：当递归处理到棋盘的最后一行时，即找到一组有效解并返回。

最后，将找到的解打印输出。理解递归调用函数的执行逻辑是掌握此算法的关键难点。

上述内容仅为解题思路，明确了需要解决的核心问题，但并不等同于程序的实际运行流程。

具体实现代码如下：

#-*- coding:utf-8 -*-
import random
#冲突检查，在定义state时，采用state来标志每个皇后的位置，其中索引用来表示横坐标，基对应的值表示纵坐标，例如： state[0]=3，表示该皇后位于第1行的第4列上
def conflict(state, nextX):
  nextY = len(state)
#  print(nextY),
  for i in range(nextY):
    #如果下一个皇后的位置与当前的皇后位置相邻（包括上下，左右）或在同一对角线上，则说明有冲突，需要重新摆放
    if abs(state[i]-nextX) in (0, nextY-i):
#纵坐标减去下一个皇后的横坐标的绝对值 处于 0到下一皇后纵坐标减i则冲突
      return True
  return False
#采用生成器的方式来产生每一个皇后的位置，并用递归来实现下一个皇后的位置。
def queens(num, state=()):
  #num = 8
#  print("%d "%len(state)),
  for pos in range(num):
    if not conflict(state, pos): #如果没有冲突
      #产生当前皇后的位置信息
      if len(state) == num-1:
        yield (pos, ) #生成元组
      #否则，把当前皇后的位置信息，添加到状态列表里，并传递给下一皇后。
      else:
        for result in queens(num, state+(pos,)):
          yield (pos, ) + result
          #result这个变量代表的是quees返回的元组
#若是最后一行 对于 pos in range(num)调用conflict(state, num) ,
#如果没有冲突,生成元组
#若不是最后一行 对于pos in range(num)调用conflict(state, pos),
#如果没有冲突,state更新,递归调用queens(num, state) state将更新
#为了直观表现棋盘，用X表示每个皇后的位置
def prettyprint(solution):
  def line(pos, length=len(solution)):
    return '. ' * (pos) + 'X ' + '. '*(length-pos-1)
  for pos in solution:
    print line(pos)
if __name__ == "__main__":#来判断是否是在直接运行该.py文件
  prettyprint(random.choice(list(queens(8))))

程序运行结果如下：