★ 第三十四讲 八皇后问题 | 【递归版】 ★

ZMichael

其实整个递归思路是这样的：
    某一行中放皇后的位置不止一个，这些可能的位置中，并不是所有的可能位置加上前面的行的皇后位置都能保证整个棋盘可以放8个皇后(即组成一个问题的解)。
   在代码中，针对某一行r的可能位置，先在其中一个放下（代码中是放在了j列），并保存当前的位置j(因为程序是递归调用，即调用函数，计算机会自动保存现场的变量)，然后递归下一行r+1。在下一行r+1中如果有可以放皇后的位置，那么就先找一个可能的位置放下，接着进入一行r+2的递归；如果在r+1行没有找到可以放皇后的位置，则本次递归返回上一行r的调用，在j的基础上查找下一个可以放皇后的位置，如果有则先放下皇后，进行下一行r+1的递归，如果找不到则返回r-1行的调用。

jadqin

有事一条小水鱼

vae弓虽ybb

。

VeryHannibal

这个算法我用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[i][col] != 0:
                flag1 = 1
                break
        
        #判断左上方
        i = row
        j = col
        while i>=0 and j>=0:
            
            if chess[i][j] != 0:
                flag2 = 1
                break
            i -= 1
            j -= 1
        
        #判断右上方
        i = row
        j = col
        while i>=0 and j<self.size:
            if chess[i][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[i])
            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][i]=0
                    chess_n[row][j]=1
                    self.nqueen(row+1, chess_n)
                else:
                    pass

nq = N_Queens(8)
nq.nqueen(0, nq.chess)

电子门外汉

RE: ★ 第三十四讲 八皇后问题 | 【递归版】 ★ [修改]

小杜2018

你好，为什么在调用notdanger函数时用的是chesss而不是chess2啊

yy五谷鱼粉

我是一只快乐的小乌龟，不怕雨。。。。

JoshuaC

11

w爱编程

谢谢

Zongminxie

加油( _)

我就23333

小呀小甲鱼

hjwwwwww

kk

yuke

l

shygjyi

初学者，进来围观

浪荡客

111

remakejobs

mark

羽艺

好，妙啊，真是妙啊，妙不可言！

xcx9977

感谢

小小鱼丸

不知道

爱喝百岁山

1