内容简介:我们来看一个有趣的问题:八皇后问题。这里的皇后是国际象棋中的皇后,虽然我只会玩中国象棋而不会玩国际象棋。这个问题和会不会国际象棋没有关系。八皇后问题描述:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。解决这个问题前,我们引入一个回溯的概念。比如我们走迷宫,前路未可知,向前走总会碰到岔路且是二选一的,我们一路选择岔路,直到发现无法走通,就回到倒数第二次的岔路继续二选一。如此往复,理论上我们最终总能走出
我们来看一个有趣的问题:八皇后问题。这里的皇后是国际象棋中的皇后,虽然我只会玩中国象棋而不会玩国际象棋。这个问题和会不会国际象棋没有关系。
八皇后问题描述:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行、纵行或斜线上。
解决这个问题前,我们引入一个回溯的概念。比如我们走迷宫,前路未可知,向前走总会碰到岔路且是二选一的,我们一路选择岔路,直到发现无法走通,就回到倒数第二次的岔路继续二选一。如此往复,理论上我们最终总能走出迷宫。
那么,八皇后问题,我们依然这样解决。首先尝试放置第一个皇后,在第一行。然后放置第二个皇后,一次类推。如果发现不能放置下一个皇后,就回溯到上一步。
下面我们开始代码实现。
我们定义是否下一个皇后放的位置是否合法。我们用数组指定每一行皇后的位置。比如state[0]=2,表示第1行第3列的位置。我们用下面的函数表示下一个皇后放置的位置是否是正确的。
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
nextX表示下一个皇后的水平位置,即x坐标。nextY表示垂直位置,即y坐标。对这两个皇后的位置做一个检查,如果下一个皇后和前面的皇后同样有同样的水平位置,或者是在一条对角线上,就表示不合法,返回True。如果检查没问题,返回False。之所以这样返回,是因为这个函数的意思本地放的位置错误。True表示真的错了,False表示没毛病。
关键的一句是:abs(state[i]-nextX) in (0,nextY-1)。下一个皇后和前一个皇后水平距离为0,或者垂直距离为0,都表示有错误。
关键的代码来了,
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
回溯的问题一定是要递归来实现,才比较方便。假定最后一个皇后的位置是正确的,需要回溯到上一步,在前面的步骤中加入if else选择位置。这里是最难理解的。
我们先这样思考,当7个皇后都放好了位置,只剩最后一个皇后了,此时有两种情况:一是,根据前7个皇后能生成出最后一个皇后的所有位置。二是最后一个皇后没地方放了。
如果是情况一,那就解决问题了,此时事情做完了。如果是情况二,那么就要回溯到第七个皇后的位置问题了。第七个皇后需要重新放一次不同位置。
调用如下,
print(len(list(queens(3)))) print(len(list(queens(4)))) print(len(list(queens(8))))
输出
八皇后有92中放法。我们用图形打印出其中一种看看,
def prettyprint(s): def line(pos,length=len(s)): return '. ' *(pos) + 'X ' +'. ' * (length-pos-1) for pos in s: print(line(pos)) import random prettyprint(random.choice(list(queens(8))))
92种中的一种图形如下,
. . . X . . . . . X . . . . . . . . . . . . X . . . X . . . . . . . . . . X . . . . . . . . . X X . . . . . . . . . . . X . . .
工程文件下载: https://download.csdn.net/download/yysyangyangyangshan/10833745
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
算法分析导论
(美)Robert Sedgewick、(法)Philippe Flajolet / 冯舜玺、李学武、裴伟东、等其他 / 机械工业出版社 / 2006-4 / 38.00元
本书阐述了用于算法数学分析的主要方法,所涉及的材料来自经典数学课题,包括离散数学、初等实分析、组合数学,以及来自经典的计算机科学课题,包括算法和数据结构,本书内容集中覆盖基础、重要和有趣的算法,前面侧重数学,后面集中讨论算法分析的应用,重点的算法分的的数学方法。每章包含大量习题以及参考文献,使读者可以更深入地理解书中的内容。 本书适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的......一起来看看 《算法分析导论》 这本书的介绍吧!