Python解决八皇后问题示例

yipeiwu_com7年前Python基础

本文实例讲述了Python解决八皇后问题的方法。分享给大家供大家参考,具体如下:

八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2。而且仅当 n2 = 1 或 n1 ≥ 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))))

运行结果:

更多关于Python相关内容感兴趣的读者可查看本站专题:《Python数据结构与算法教程》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

相关文章

python3实现在二叉树中找出和为某一值的所有路径(推荐)

python3实现在二叉树中找出和为某一值的所有路径(推荐)

请写一个程序创建一棵二叉树,并按照一定规则,输出二叉树根节点到叶子节点的路径。 规则如下: 1、从最顶端的根结点,到最下面的叶子节点,计算路径通过的所有节点的和,如果与设置的某一值的相同...

python实现的重启关机程序实例

本文实例讲述了Python实现的重启关机程序的方法,对Python程序设计有一定的参考价值。具体方法如下: 实例代码如下: #!/usr/bin/python #coding=utf...

Python闭包思想与用法浅析

本文实例讲述了Python闭包思想与用法。分享给大家供大家参考,具体如下: 浅谈 python 的闭包思想 首先 python的闭包使用方法是:在方法A内添加方法B,然后return 方...

django连接mysql数据库及建表操作实例详解

django连接mysql数据库及建表操作实例详解

本文实例讲述了django连接mysql数据库及建表操作。分享给大家供大家参考,具体如下: django连接mysql数据库需要在project同名的目录下面的__init__.py里面...

selenium+python实现自动登录脚本

os:windows 前提:Python,selenium,IEDriverServer.exe,ie浏览器 首先安装Python2.7 安装成功后,计算机联网状态下在cmd命令行下输入...