鱼C论坛

 找回密码
 立即注册
楼主: 不二如是

[学习笔记] ★ 第三十四讲 八皇后问题 | 【递归版】 ★

[复制链接]
发表于 2018-9-14 21:58:17 | 显示全部楼层
本帖最后由 ZMichael 于 2018-9-14 22:01 编辑

其实整个递归思路是这样的:
    某一行中放皇后的位置不止一个,这些可能的位置中,并不是所有的可能位置加上前面的行的皇后位置都能保证整个棋盘可以放8个皇后(即组成一个问题的解)。
   在代码中,针对某一行r的可能位置,先在其中一个放下(代码中是放在了j列),并保存当前的位置j(因为程序是递归调用,即调用函数,计算机会自动保存现场的变量),然后递归下一行r+1。在下一行r+1中如果有可以放皇后的位置,那么就先找一个可能的位置放下,接着进入一行r+2的递归;如果在r+1行没有找到可以放皇后的位置,则本次递归返回上一行r的调用,在j的基础上查找下一个可以放皇后的位置,如果有则先放下皇后,进行下一行r+1的递归,如果找不到则返回r-1行的调用。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-10-27 09:07:27 | 显示全部楼层
有事一条小水鱼
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-10-30 20:11:58 From FishC Mobile | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-11-17 04:06:20 | 显示全部楼层
本帖最后由 VeryHannibal 于 2021-6-9 23:13 编辑

这个算法我用python实现了一下,发先在判断是否危险的那个函数里 只需要验证左上角,右上角和整个一列就可以,没必要验证左下角和右下角。因为,我们是一行一行去放置皇后的,比如当我们放到第4行的时候 后面4行还没有放置,所以没必要验证。以下为python版的代码:
#八皇后问题:

from copy import deepcopy

class N_Queens():
    def __init__(self, n):
        self.count = 0
        self.size = n
        self.chess = [[0 for i in range(n)] for j in range (n)]
        self.solutions = []


    def judge(self, row, col, chess):
        
        flag1=0
        flag2=0
        flag3=0
        #flag4=0
        #flag5=0
        
        #判断一整列
        for i in range(self.size):
            if chess[col] != 0:
                flag1 = 1
                break
        
        #判断左上方
        i = row
        j = col
        while i>=0 and j>=0:
            
            if chess[j] != 0:
                flag2 = 1
                break
            i -= 1
            j -= 1
        
        #判断右上方
        i = row
        j = col
        while i>=0 and j<self.size:
            if chess[j] != 0:
                flag3 = 1
                break
            i -= 1
            j += 1
        
        
        if (flag1 or flag2 or flag3):# or flag4 or flag5):
            return False
        else:
            return True
        
         
   
    def nqueen(self, row, chess):
        chess_n = deepcopy(chess)
        if row == self.size:
            print('第%d种结果:'%(self.count+1))
            for i in range(self.size):
                print(chess_n)
            print('\n')
            self.solutions.append(chess_n)
            self.count+=1
        
        else:
            for j in range(self.size):
                if self.judge(row, j, chess):
                    for i in range(self.size):
                        chess_n[row]=0
                    chess_n[row][j]=1
                    self.nqueen(row+1, chess_n)
                else:
                    pass

nq = N_Queens(8)
nq.nqueen(0, nq.chess)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-11-19 11:09:05 | 显示全部楼层
RE: ★ 第三十四讲 八皇后问题 | 【递归版】 ★ [修改]
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-12-2 17:29:17 | 显示全部楼层
你好,为什么在调用notdanger函数时用的是chesss而不是chess2啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-12-10 23:03:39 | 显示全部楼层
我是一只快乐的小乌龟,不怕雨。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-12-11 19:54:52 | 显示全部楼层
11
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-12-28 18:56:28 | 显示全部楼层
谢谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-12-29 14:59:29 From FishC Mobile | 显示全部楼层
加油( _)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-1-31 10:33:56 | 显示全部楼层
小呀小甲鱼
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-1-31 21:52:02 | 显示全部楼层
kk
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-2-18 11:00:44 | 显示全部楼层
l
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-2-18 15:36:17 | 显示全部楼层
初学者,进来围观
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-4-15 21:16:58 | 显示全部楼层
111
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-5-14 17:03:48 | 显示全部楼层
mark
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-5-16 22:32:05 | 显示全部楼层
好,妙啊,真是妙啊,妙不可言!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-8-20 12:04:32 | 显示全部楼层
感谢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-9-17 16:59:37 | 显示全部楼层
不知道
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-9-18 11:54:08 | 显示全部楼层
1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 12:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表