本帖最后由 ZMichael 于 2018-9-14 22:01 编辑
其实整个递归思路是这样的：
某一行中放皇后的位置不止一个，这些可能的位置中，并不是所有的可能位置加上前面的行的皇后位置都能保证整个棋盘可以放8个皇后(即组成一个问题的解)。
在代码中，针对某一行r的可能位置，先在其中一个放下（代码中是放在了j列），并保存当前的位置j(因为程序是递归调用，即调用函数，计算机会自动保存现场的变量)，然后递归下一行r+1。在下一行r+1中如果有可以放皇后的位置，那么就先找一个可能的位置放下，接着进入一行r+2的递归；如果在r+1行没有找到可以放皇后的位置，则本次递归返回上一行r的调用，在j的基础上查找下一个可以放皇后的位置，如果有则先放下皇后，进行下一行r+1的递归，如果找不到则返回r-1行的调用。
有事一条小水鱼
。
本帖最后由 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 = [ 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 != 0:
flag1 = 1
break
#判断左上方
i = row
j = col
while i>=0 and j>=0:
if chess != 0:
flag2 = 1
break
i -= 1
j -= 1
#判断右上方
i = row
j = col
while i>=0 and j<self.size:
if chess != 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=0
chess_n=1
self.nqueen(row+1, chess_n)
else:
pass
nq = N_Queens(8)
nq.nqueen(0, nq.chess)
RE: ★ 第三十四讲 八皇后问题 | 【递归版】 ★ [修改]
你好，为什么在调用notdanger函数时用的是chesss而不是chess2啊
我是一只快乐的小乌龟，不怕雨。。。。
11
谢谢
加油( _)
小呀小甲鱼
kk
l
初学者，进来围观
111
mark
好，妙啊，真是妙啊，妙不可言！
感谢
不知道
1