n皇后(回溯法+分支限界)

问题描述:略;

输入皇后数量n;

输出的第i个数字j,表示第i行第j列放置皇后。

通常n皇后问题被当做回溯法的入门题目,而回溯法和分支限界有着很多相似和不同。在此,基于Python,通过n皇后这个问题简单阐述回溯法和分支限界之间的关系。

1.回溯法:

回溯法就是使用深度优先的搜索策略搜索解空间,在搜索过程中构造的二叉树,称为解空间树。在搜索的过程中,遇到符合条件的结点,就继续搜寻其下一个结点(左子树),不符合剪枝函数的时候,就向前回溯,遍历另外一半解空间(右子树),直到符合递归出口条件。最终得到问题的所有解

def setQueen(cur):
    if cur == n: # 递归结束
        #print("+1")
        print(result)
        global tot
        tot += 1
        return
    else:    
        for i in range(0,n):# 检测是否会与其他皇后攻击
            ok = 1
            result[cur] = i
            for j in range(0,cur):
                if result[cur] == result[j] or cur-result[cur] == j-result[j] or cur+result[cur] == j+result[j]  :
                    ok = 0
                    result[cur] ="*"
                    break
            if ok == 1:
                #print("ok")
                print(result)
                setQueen(cur+1)

2.分支限界:

分支限界与回溯法相似,不同在于其搜索策略使用广度优先,得到的解也是一个符合条件的解。实现的时候,分支限界通常采用队列和循环结构。详情请见代码注释。

n = int(input())
class Node():# 节点类
    cur = -1 # 当前是第cur个皇后,cur值通过调用赋值
    l = [-1 for i in range(n)] # 当前节点保存的放置情况
q = []
node = Node()
node.cur = 0
q.append(node) # 将首个结点入队
while(True):
    cur_Node = q.pop(0) # 获取队头结点,作为活结点
    cur_list = cur_Node.l.copy()
    cur = cur_Node.cur
    #print("获取:",cur_list)
    if cur == n:
        #print("退出")
        break
    for i in range(n): # 遍历列看看哪一列没有放皇后
        # i 是列数
        cur_list[cur] = i # 放置皇后
        ok = True 
        for j in range(cur): # 判断斜线上是否有冲突
            if cur_list[cur] == cur_list[j] or cur-cur_list[cur]==j-cur_list[j] or cur+cur_list[cur] == j+cur_list[j] :# 相等则斜线上有碰撞
                ok = False
                break
        if ok == True:
            node = Node()                                                           #不相等则说明符合条件,不需要剪枝
            node.cur = cur+1
            node.l = cur_list.copy()# 血的教训告诉我们要用copy,不然会错
            q.append(node)
#print("最终结果:",cur_list)
for i in cur_list:
    print(i+1,end=" ")

发表评论

电子邮件地址不会被公开。 必填项已用*标注