`

八皇后问题

阅读更多
# coding: utf-8
__author__ = 'Administrator'


# 冲突函数
# 如果下一个皇后和正在考虑的前一个皇后的水平距离为0,
# 或者等于垂直距离(在一条对角线上),返回True
def conflict(state, nextX):
    nextY = len(state)
    for i in range(nextY):
        if abs(state[i] - nextX) in (0, nextY - i):
            return True
    return False


# num:皇后的总数
# state:已经注册了的每行的皇后的位置列表(X坐标)
def queens(num=8, state=()):
    print(state)
    find = False
    for pos in range(num):
        if not conflict(state, pos):
            find = True
            if len(state) == num - 1:
                # 如果state大小已经是num-1了,那么yield最后一个位置
                yield (pos,)
            else:
                for result in queens(num, state + (pos,)):
                    yield (pos,) + result
    if not find:
        print("HO, NO..." + str(state))

print(list(queens(4)))

 

回溯法原理:

打个比方,想象一下你要出席一个很重要的会议,但你不知道在哪儿开会,在你面前有两扇门,开会地点就在其中一扇门后面,于是有人挑了左边的进入,然后又发现两扇门,后来再选了左边的门,结果却错了,于是回溯到刚才的两扇门那里,并选择右边的门,结果还是错的,于是再次回溯,直到回到开始点,在那里选择了右边的门。

 

比较难理解的是这两行代码:

for result in queens(num, state + (pos,)):

递归的调用queens生成器,将state + (pos)当做参数传给queens,state是已经存在的合法状态列表,而pos是对要操作的该行进行遍历的位置参数,请注意state + (pos) 并没有将它赋值给state,是因为如果后面的返回没有合法值的话可以回溯到前面的状态,也就是说这次迭代里面我并没有说pos是合法状态,只是可能是合法状态,那么当往下的迭代无合法值,一级一级的跳出的时候,每次跳到一级,这个state都是合法的状态。

 

yield (pos,) + result:

这行的意思是我将当前状态pos作为前缀再加上一直到到底的迭代位置序列,也就是正序排列位置。就好比是这样的调用:(0+(1+(2+(3+(.....))))),这样够清楚了吧。^_^

 

本人博客已搬家,新地址为:http://www.pycoding.com/

分享到:
评论

相关推荐

    mfc实现八皇后问题

    八皇后问题是一个经典的计算机编程问题,它涉及到回溯算法、数据结构和图形用户界面的设计。在C++中,特别是结合MFC(Microsoft Foundation Classes)框架,可以创建具有用户友好界面的程序来解决此问题。 首先,...

    爬山法、模拟退火法、遗传算法实现八皇后问题

    它们被应用于解决各种复杂问题,包括经典的八皇后问题。八皇后问题是一个著名的棋盘放置问题,要求在8×8的棋盘上摆放8个皇后,使得任意两个皇后都不能在同一行、同一列或同一对角线上。下面将详细解释这些方法以及...

    八皇后问题详细的解法-23页 PPT PDF版.pdf

    ### 八皇后问题详解 #### 一、八皇后问题背景 八皇后问题是一个经典的计算机科学问题,也是数学领域中一个有趣的挑战。这个问题来源于国际象棋的背景:如何在一个8×8的国际象棋棋盘上放置八个皇后,使得没有任何...

    八皇后问题 c++ 八皇后问题 c++

    八皇后问题 c++ 八皇后问题 c++ 八皇后问题 c++

    八皇后问题回溯求解 matlab

    用回溯求解法求解八皇后问题,经典问题matlab实现,欢迎大家下载

    数据结构八皇后问题实验报告

    数据结构八皇后问题实验报告是一份详尽的项目文档,主要涵盖了八皇后问题的解决方案,该问题是一个经典的计算机科学和算法问题,源自国际象棋。报告的作者花费了两周时间完成,显然投入了大量的精力和思考。 八皇后...

Global site tag (gtag.js) - Google Analytics