Python实现八皇后问题示例代码

八皇后问题描述

问题: 国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子。皇后这种棋子可以攻击同一行或者同一列或者斜线(左上左下右上右下四个方向)上的棋子。在一个棋盘上如果要放八个皇后,使得她们互相之间不能攻击(即任意两两之间都不同行不同列不同斜线),求出一种(进一步的,所有)布局方式。

首先,我们想到递归和非递归两类算法来解决这个问题。首先说说递归地算法。

很自然的,我们可以基于行来做判断标准。八个皇后都不同行这是肯定的,也就说每行有且仅有一个皇后,问题就在于皇后要放在哪个列。当然八个列下标也都不能有相同,除此之外还要保证斜线上不能有重叠的皇后。

第一个需要解决的小问题就是,如何用数学的语言来表述斜线上重叠的皇后。其实我们可以看到,对于位于(i,j)位置的皇后而言,其四个方向斜线上的格子下标分别是 (i-n,j+n), (i-n,j-n), (i+n,j-n), (i+n,j+n)。当然i和j的±n都要在[0,7]的范围内,保持不越界。暂时抛开越界限制不管,这个关系其实就是: 目标格子(a,b)和本格子(i,j)在同一条斜线上 等价于 |a - i| == |b - j| 。

然后,从递归的思想来看,我们在从第一行开始给每一行的皇后确定一个位置。每来到新的一行时,对本行的所有可能位置(皇后放在这个位置和前面所有已放置的皇后无冲突)分别进行递归地深入;若某一行可能的位置数为0,则表明这是一条死路,返回上一层递归寻找其他办法;若来到的这一行是第九行(不存在第九行,只不过是说明前八行都已经正确配置,已经得到一个解决方案),这说明得到解决方案。

可以看到,寻找一行内皇后应该摆放的位置这是个递归过程,并且在进入递归时,应该要告诉这个过程的东西包括两个: 1. 之前皇后放置的状态, 2. 现在是第几行。

所以,递归主体函数可以设计为 EightQueen(board, row),其中board表示的是当前棋盘的状态(比如一个二维数组,0表示未放置,1表示放有皇后的状态)。另外还可以有一个check(board,pos),pos可以是一个(x,y)元组,check函数用来返回以当前的board棋盘状态,如果在pos再放置一个皇后是否会有冲突。

基于上面的想法,初步实现如下:

def check(board,pos):
 # check函数暂时先不实现
 pass

def EightQueen(board,row):
 blen = len(board)
 if row == blen: # 来到不存在的第九行了
  print board
  return True # 一定要return一个True,理由在下面
 for possibleY in range(blen):
  if check(board,(row,possibleY)):
   board[row][possibleY] = 1 # 放置一个Queen
   if not EightQueen(board,row+1): # 这里其实是本行下面所有行放置皇后的递归入口。但是如果最终这条路没有找到一个解,那么
    # 此时应该将刚才放置的皇后收回,再去寻找下一个可能的解
    board[row][possibleY] = 0
   else:
    return True
 return False

最开始,可能在回归返回条件那里面不会想到要return True,而只是return。对应的,下面主循环中放置完Queen之后也只是简单地递归调用EightQueen,不会做逻辑判断。但是很快可以发现这样做存在一个问题,即当某一层递归中for possibleY这个循环走完却没有找到一个合适的解(即本行无合适位置),此时返回上一行,上一行的possibleY右移一格,此时之前放在这一行的Queen的位置仍然是1。这样之后本行的所有check肯定都是通不过的。所以我们需要设计一个机制,使得第一个possibleY没有找到合理的最终解决方案(这里就加上了一个判断条件),要右移一格到下一个possibleY时将本格的Queen收回。

这个判断条件就是如果某层递归for possibleY循环整个走完未找到结果返回False(EightQueen整个函数最后的返回),上一层根据这个False反馈把前一个Queen拿掉;如果找到了某个结果那么就可以一路return True回来,结束函数的运行。

另外,如果只是获取一个解的话,可以考虑在if row == blen的时候,打印出board,然后直接sys.exit(0)。此时就只需要for possibleY循环完了之后return一个False就可以了。当然主循环中对于递归的返回的判断 if not EightQueen还是需要的。

上面没有实现check函数。其实仔细想一下,如果按照上面的设想来实现check函数还是有点困难的。比如令 x,y = pos,尽管此时我们只需要去检查那些行下标小于x的board中的行,但是对于每一行中我们还是要一个个去遍历,找到相关行中值是1的那个格子(突然发现这个是one-hot模式诶哈哈),然后将它再和x,y这个位置做冲突判断。所以但是这个check函数复杂度就可能会达到O(n^2),再套上外面的循环,复杂度蹭蹭往上涨。下面是check函数的一个可能的实现:

def check(board,pos):
 x,y = pos
 blen = len(board)
 for i in range(x):
  for j in range(blen):
   if board[i][j] == 1:
    if j == y or abs(j-y) == abs(i-x):
     return False
 return True

其实可以看到,我们花了一层循环在寻找某行中的one-hot,那些大量的0值元素是我们根本不关心的。换句话说,对于board这个二维数组,其实我们真正关心的是每行中one-hot值的下标值。自然我们就可以想到,能不能将board转化为一个一维数组,下标本身就代表了board中的某一行,然后值是指这一行中皇后放在第几列。

如果是这样的话,那么程序就需要改造,首先是check函数要根据新的board数据结构做一些调整:

def check(board,row,col):
 i = 0
 while i < row:
  if abs(col-board[i]) in (0,abs(row-i)):
   return False
  i += 1
 return True

可以看到,改变二维数组board变为一维数组之后,我们可以在O(1)的时间就确定row行之前每一行摆放的位置,并将其作为参考进行每一行的冲突判断。

然后是主函数的修改:

def EightQueen(board,row):
 blen = len(board)
 if row == blen: # 来到不存在的第九行了
  print board
  return True
 col = 0
 while col < blen:
  if check(board,row,col):
   board[row] = col
   if EightQueen(board,row+1):
    return True
  col += 1
 return False

def printBoard(board):
 '''为了更友好地展示结果 方便观察'''
 import sys
 for i,col in enumerate(board):
  sys.stdout.write('□ ' * col + '■ ' + '□ ' * (len(board) - 1 - col))
  print ''

总的结构,和没修改之前是类似的,只不过在主循环中,从上面的possibleY作为游标去设置 - 去除 一个位置的放置状态,这种方式改为了简单的col += 1。改成col+=1的好处就是当某轮递归以失败告终,返回上层递归之后,就不用再去特地收回之前放置好的Queen,而是可以直接让col += 1,。

printBoard函数可以将一维数组的board状态很直观地展现出来:

■ □ □ □ □ □ □ □
□ □ □ □ ■ □ □ □
□ □ □ □ □ □ □ ■
□ □ □ □ □ ■ □ □
□ □ ■ □ □ □ □ □
□ □ □ □ □ □ ■ □
□ ■ □ □ □ □ □ □
□ □ □ ■ □ □ □ □

所有结果

上面的程序多只是生成了一个结果,而实际上八皇后可以有很多种可能的布局。如何才能求得所有结果?其实只要小小地修改一下上面的程序就可以了。

以上面修改过后一维数组维护棋盘状态为例。程序在碰到一次row == blen的情况之后就返回了True,然后递归一层层地返回True直到最上层。所以找到一个解决方案之后,程序就会退出了。

反过来,如果获得一个解决方案之后,不判断EightQueen函数的返回,此时函数会继续执行col += 1,将状态搜寻继续下去,如此收集状态的任务在row == blen的判断中,(注意这里的return可不能删,这里需要一个return来提示递归的终结条件),而对于每条递归路径总是穷尽所有可能再回头,这样就可以获得到所有可能了:

def EightQueen(board,row):
 blen = len(board)
 if row == blen: # 来到不存在的第九行了
  print board
  return True
 col = 0
 while col < blen:
  if check(board,row,col):
   board[row] = col
   if EightQueen(board,row+1):
    # return True 去掉这里即可,或者直接删除掉整个判断,只留下单一个EightQueen(board,row+1)
    pass
  col += 1
 return False

示例结果:

[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]
…… 总共有92种布局方案

非递归

非递归解这个问题,很显然是要去维护一个stack来保存一个路径了。简单来说,这个栈中维护的应该是“尚未尝试去探索的可能”,当我开始检查一个特定的位置,如果检查通过,那么应该做的是首先将本位置右边一格加入栈,然后再把下一行的第一个格子加入栈。注意前半个操作很容易被忽视,但是如果不将本位置右边一格入栈,那么如果基于本格有皇后的情况进行的递归最终没有返回一个结果的话,接下来就不知道往哪走了。如果使用了栈,那么用于扫描棋盘的游标就不用自己在循环里+=1了,循环中游标的移动全权交给栈去维护。

代码如下:

def EightQueen(board):
 blen = len(board)
 stack = Queue.LifoQueue()
 stack.put((0,0)) # 为了自洽的初始化
 while not stack.empty():
  i,j = stack.get()
  if check(board,i,j): # 当检查通过
   board[i] = j # 别忘了放Queen
   if i >= blen - 1:
    print board # i到达最后一行表明已经有了结果
    break
   else:
    if j < blen - 1: # 虽然说要把本位置右边一格入栈,但是如果本位置已经是行末尾,那就没必要了
     stack.put((i,j+1))
    stack.put((i+1,0)) # 下一行第一个位置入栈,准备开始下一行的扫描
  elif j < blen - 1:
   stack.put((i,j+1)) # 对于未通过检验的情况,自然右移一格即可

显然,把break去掉就是求所有解了

C语言版

#include <stdio.h>

static int board[8] = {};
int board_size = sizeof(board)/sizeof(int);

int check(int *board,int row){
 int i = 0;
 while(i < row){
  if(board[i] == board[row] || row - i == board[row] - board[i] || row - i == board[i] - board[row]){
   return 0;
  }
  i++;
 }
 // printf("board[%d]: %d\n",row,board[row]);
 return 1;
}

void print_board(int *board){
 int i;
 int size = board_size;
 for(i=0;i<size;i++){
  printf("%d,",board[i]);
 }
 printf("\n");
 i = 0;
 while (i < size){
  int j;
  for (j=0;j<size;j++){
   if(j == board[i]){
    printf("%s ","■ ");
   }
   else{
    printf("%s ","□ ");
   }
  }
  printf("\n");
  i++;
 }
}

int eight_queen(int *board,int row){
 if (row == 8){
  print_board(board);
  return 1;
 }
 board[row] = 0;
 while (1){
  if (check(board,row) && eight_queen(board,row+1)){
    return 1;
  }
  else{
   if(++board[row] >= 8){
    break;
   }
  }
 }

 return 0;
}

int main(){
 eight_queen(board,0);
 // print_board(board);
 return 0;
}

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对我们的支持。

(0)

相关推荐

  • 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(

  • python八皇后问题的解决方法

    本文为大家分享了python八皇后问题的解决方法,供大家参考,具体内容如下 题目: 给定一个 N*N 正方形棋盘,在上面放置 N个棋子,又叫皇后,使每两个棋子都不在同一条横线上.竖线上.斜线上.一般我们都讨论8皇后,但是只要N > 4,都会存在解的. 分析: 方法1:根据定义来处理,即每往棋盘中放置皇后的时候,都要判断哪些位置可以放新加入的皇后,而哪些地方如果放置皇后的话,会造成冲突.我下面写的这个代码就是基于此. 方法2.我看了下别人的优化,主要是采用位运算来实现计算复杂度降低的,我没有用Py

  • Python解决八皇后问题示例

    本文实例讲述了Python解决八皇后问题的方法.分享给大家供大家参考,具体如下: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2.而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解. 这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方

  • Python八皇后问题解答过程详解

    最近看Python看得都不用tab键了,哈哈.今天看了一个经典问题--八皇后问题,说实话,以前学C.C++的时候有这个问题,但是当时不爱学,没搞会,后来算法课上又碰到,只是学会了思想,应该是学回溯法的时候碰到的.八皇后问题是说要在一个棋盘上放置8个皇后,但是不能发生战争,皇后们都小心眼,都爱争风吃醋,如果有人和自己在一条线上(水平.垂直.对角线)就会引发撕13大战,所以我们就是要妥当的安排8位娘娘,以保后宫太平. 言归正传,首先,我们得想好解决方案怎么表示,这种事首先想到列表,当然规模小的话用元

  • python基于右递归解决八皇后问题的方法

    本文实例讲述了python基于右递归解决八皇后问题的方法.分享给大家供大家参考.具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多. def Test(queen,n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q=queen[n] for i in xrange(n): if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i

  • Python实现八皇后问题示例代码

    八皇后问题描述 问题: 国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子.皇后这种棋子可以攻击同一行或者同一列或者斜线(左上左下右上右下四个方向)上的棋子.在一个棋盘上如果要放八个皇后,使得她们互相之间不能攻击(即任意两两之间都不同行不同列不同斜线),求出一种(进一步的,所有)布局方式. 首先,我们想到递归和非递归两类算法来解决这个问题.首先说说递归地算法. 很自然的,我们可以基于行来做判断标准.八个皇后都不同行这是肯定的,也就说每行有且仅有一个皇后,问题就在于皇后要放在哪个列.当然八个列下

  • 基于Python实现围棋游戏的示例代码

    目录 1.导入模块 2.初始化棋盘 3. 开始游戏 4.放弃当前回合落子 5.悔棋判断 6.重新开始 7.右侧太极图的设置 8.落子设置 9.吃子规则判定设置 10.其他 11.程序入口 12.效果图 文件自取 1.导入模块 tkinter:ttk覆盖tkinter部分对象,ttk对tkinter进行了优化 copy:深拷贝时需要用到copy模块 tkinter.messagebox:围棋应用对象定义 如没有以上模块,在pycharm终端输入以下指令: pip install 相应模块 -i h

  • Python+turtle绘制对称图形的示例代码

    目录 1.图1 2.图2 3.图3 4.图4 5.图5 6.图6 最近有个朋友,想要我帮忙用python画几个图,在画的过程中觉得有些图还挺有意思的,分享给大家. 1.图1 第一个图是由三角形组成的花,感兴趣的小伙伴可以自己尝试在python中用turtle库绘制一下. 具体代码如下: # -*- coding: UTF-8 -*- ''' 代码用途 :画对称图形 作者 :阿黎逸阳 博客 : https://blog.csdn.net/qq_32532663/article/details/10

  • Python实现登录接口的示例代码

    之前写了Python实现登录接口的示例代码,最近需要回顾,就顺便发到随笔上了 要求: 1.输入用户名和密码 2.认证成功,显示欢迎信息 3.用户名3次输入错误后,退出程序 4.密码3次输入错误后,锁定用户名 Readme: 1.UserList.txt 是存放用户名和密码的文件,格式为:username: password,每行存放一条用户信息 2.LockList.txt 是存放已被锁定用户名的文件,默认为空 3.用户输入用户名,程序首先查询锁定名单 LockList.txt,如果用户名在里面

  • python实现log日志的示例代码

    源代码: # coding=utf-8 import logging import os import time LEVELS={'debug':logging.DEBUG,\ 'info':logging.INFO,\ 'warning':logging.WARNING,\ 'error':logging.ERROR,\ 'critical':logging.CRITICAL,} logger=logging.getLogger() level='default' def createFile

  • Python中字符串与编码示例代码

    在最新的Python 3版本中,字符串是以Unicode编码的,即Python的字符串支持多语言 编码和解码 字符串在内存中以Unicode表示,在操作字符串时,经常需要str和bytes互相转换   如果在网络上传输或保存到磁盘上,则从内存读到的数据就是str,要把str变为以字节为单位的bytes,称为编码   如果从网络或磁盘上读取字节流,则从网络或磁盘上读到的数据就是bytes,要把bytes变为str,称为解码   为避免乱码问题,应当始终坚持使用UTF-8编码对str和bytes进行

  • python+selenium+chromedriver实现爬虫示例代码

    下载好所需程序 1.Selenium简介 Selenium是一个用于Web应用程序测试的工具,直接运行在浏览器中,就像真正的用户在操作一样. 2.Selenium安装 方法一:在Windows命令行(cmd)输入pip install selenium即可自动安装,安装完成后,输入pip show selenium可查看当前的版本 方法二:直接下载selenium包: selenium下载网址 Pychome安装selenium如果出现无法安装,参考以下博客 解决Pycharm无法使用已经安装S

  • Python实现ElGamal加密算法的示例代码

    在密码学中,ElGamal加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法.它在1985年由塔希尔·盖莫尔提出.GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法. ElGamal加密算法可以定义在任何循环群G上.它的安全性取决于G上的离散对数难题. 使用Python实现ElGamal加密算法,完成加密解密过程,明文使用的是125位数字(1000比特). 代码如下: import random from math import pow a = random.randint(2

  • Python操作MySQL数据库的示例代码

    1. MySQL Connector 1.1 创建连接 import mysql.connector config={ "host":"localhost","port":"3306", "user":"root","password":"password", "database":"demo" } con=

随机推荐