Python基于生成器迭代实现的八皇后问题示例

yipeiwu_com5年前Python基础

本文实例讲述了Python基于生成器迭代实现的八皇后问题。分享给大家供大家参考,具体如下:

问题:有一个棋盘和8个要放到上面的皇后,唯一的要求是皇后之间不能形成威胁。也就是说,必须把他们防止成每个皇后都不能吃掉其他皇后的状态。

# -*- coding: utf-8 -*-
#python 2.7.13
__metaclass__ = type
def confict(state, nextX):
  nextY = len(state)
  for i in range(nextY):
    if abs(state[i] - nextX) in (0, nextY - i):
      return True
  return False
def queens(num=8, state=()):
  for pos in range(num):
    if not confict(state, pos):
      if len(state) == num -1:
        yield (pos,)
      else:
        for result in queens(num, state + (pos,)):
          yield (pos,) + result
print list(queens()) #打印输出

运行结果:

[(0, 4, 7, 5, 2, 6, 1, 3), (0, 5, 7, 2, 6, 3, 1, 4), (0, 6, 3, 5, 7, 1, 4, 2), (0, 6, 4, 7, 1, 3, 5, 2), (1, 3, 5, 7, 2, 0, 6, 4), (1, 4, 6, 0, 2, 7, 5, 3), (1, 4, 6, 3, 0, 7, 5, 2), (1, 5, 0, 6, 3, 7, 2, 4), (1, 5, 7, 2, 0, 3, 6, 4), (1, 6, 2, 5, 7, 4, 0, 3), (1, 6, 4, 7, 0, 3, 5, 2), (1, 7, 5, 0, 2, 4, 6, 3), (2, 0, 6, 4, 7, 1, 3, 5), (2, 4, 1, 7, 0, 6, 3, 5), (2, 4, 1, 7, 5, 3, 6, 0), (2, 4, 6, 0, 3, 1, 7, 5), (2, 4, 7, 3, 0, 6, 1, 5), (2, 5, 1, 4, 7, 0, 6, 3), (2, 5, 1, 6, 0, 3, 7, 4), (2, 5, 1, 6, 4, 0, 7, 3), (2, 5, 3, 0, 7, 4, 6, 1), (2, 5, 3, 1, 7, 4, 6, 0), (2, 5, 7, 0, 3, 6, 4, 1), (2, 5, 7, 0, 4, 6, 1, 3), (2, 5, 7, 1, 3, 0, 6, 4), (2, 6, 1, 7, 4, 0, 3, 5), (2, 6, 1, 7, 5, 3, 0, 4), (2, 7, 3, 6, 0, 5, 1, 4), (3, 0, 4, 7, 1, 6, 2, 5), (3, 0, 4, 7, 5, 2, 6, 1), (3, 1, 4, 7, 5, 0, 2, 6), (3, 1, 6, 2, 5, 7, 0, 4), (3, 1, 6, 2, 5, 7, 4, 0), (3, 1, 6, 4, 0, 7, 5, 2), (3, 1, 7, 4, 6, 0, 2, 5), (3, 1, 7, 5, 0, 2, 4, 6), (3, 5, 0, 4, 1, 7, 2, 6), (3, 5, 7, 1, 6, 0, 2, 4), (3, 5, 7, 2, 0, 6, 4, 1), (3, 6, 0, 7, 4, 1, 5, 2), (3, 6, 2, 7, 1, 4, 0, 5), (3, 6, 4, 1, 5, 0, 2, 7), (3, 6, 4, 2, 0, 5, 7, 1), (3, 7, 0, 2, 5, 1, 6, 4), (3, 7, 0, 4, 6, 1, 5, 2), (3, 7, 4, 2, 0, 6, 1, 5), (4, 0, 3, 5, 7, 1, 6, 2), (4, 0, 7, 3, 1, 6, 2, 5), (4, 0, 7, 5, 2, 6, 1, 3), (4, 1, 3, 5, 7, 2, 0, 6), (4, 1, 3, 6, 2, 7, 5, 0), (4, 1, 5, 0, 6, 3, 7, 2), (4, 1, 7, 0, 3, 6, 2, 5), (4, 2, 0, 5, 7, 1, 3, 6), (4, 2, 0, 6, 1, 7, 5, 3), (4, 2, 7, 3, 6, 0, 5, 1), (4, 6, 0, 2, 7, 5, 3, 1), (4, 6, 0, 3, 1, 7, 5, 2), (4, 6, 1, 3, 7, 0, 2, 5), (4, 6, 1, 5, 2, 0, 3, 7), (4, 6, 1, 5, 2, 0, 7, 3), (4, 6, 3, 0, 2, 7, 5, 1), (4, 7, 3, 0, 2, 5, 1, 6), (4, 7, 3, 0, 6, 1, 5, 2), (5, 0, 4, 1, 7, 2, 6, 3), (5, 1, 6, 0, 2, 4, 7, 3), (5, 1, 6, 0, 3, 7, 4, 2), (5, 2, 0, 6, 4, 7, 1, 3), (5, 2, 0, 7, 3, 1, 6, 4), (5, 2, 0, 7, 4, 1, 3, 6), (5, 2, 4, 6, 0, 3, 1, 7), (5, 2, 4, 7, 0, 3, 1, 6), (5, 2, 6, 1, 3, 7, 0, 4), (5, 2, 6, 1, 7, 4, 0, 3), (5, 2, 6, 3, 0, 7, 1, 4), (5, 3, 0, 4, 7, 1, 6, 2), (5, 3, 1, 7, 4, 6, 0, 2), (5, 3, 6, 0, 2, 4, 1, 7), (5, 3, 6, 0, 7, 1, 4, 2), (5, 7, 1, 3, 0, 6, 4, 2), (6, 0, 2, 7, 5, 3, 1, 4), (6, 1, 3, 0, 7, 4, 2, 5), (6, 1, 5, 2, 0, 3, 7, 4), (6, 2, 0, 5, 7, 4, 1, 3), (6, 2, 7, 1, 4, 0, 5, 3), (6, 3, 1, 4, 7, 0, 2, 5), (6, 3, 1, 7, 5, 0, 2, 4), (6, 4, 2, 0, 5, 7, 1, 3), (7, 1, 3, 0, 6, 4, 2, 5), (7, 1, 4, 2, 0, 6, 3, 5), (7, 2, 0, 5, 1, 4, 6, 3), (7, 3, 0, 2, 5, 1, 6, 4)]

输出列表长度:

print len(list(queens()))# 输出:92

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

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

相关文章

详解python3中socket套接字的编码问题解决

一、TCP 1、tcp服务器创建 #创建服务器 from socket import * from time import ctime #导入ctime HOST = ''...

python 定义n个变量方法 (变量声明自动化)

code: for i in range(100): cmd = "t%s = 1" % i exec cmd eval("t%s" % i) print t10 输出...

Django框架中处理URLconf中特定的URL的方法

有时你有一个模式来处理在你的URLconf中的一系列URL,但是有时候需要特别处理其中的某个URL。 在这种情况下,要使用将URLconf中把特殊情况放在首位的线性处理方式 。 比方说,...

快速了解Python开发中的cookie及简单代码示例

快速了解Python开发中的cookie及简单代码示例

cookie :是用户保存在用户浏览器端的一对键值对,是为了解决http的无状态连接。服务端是可以把 cookie写到用户浏览器上,用户每次发请求会携带cookie。 存放位置: 每...

Django将默认的SQLite更换为MySQL的实现

1、注释默认的SQLite3配置: blogproject/settings.py ''' DATABASES = { 'default': { 'ENGINE': 'djan...