最近学习了“图”的数据结构相关知识，对深度优先和广度优先有了全新认识，所以重新用DPS递归加回溯求解八皇后问题，并将之推广到N皇后。
基本思路：
- 构建N皇后求解的结果数据结构，因为N皇后必然是N行中每行一个，而只需遍历求解纵坐标，所以定义N皇后的结果数据结构为一个 len= N 列表，用于存储第N个皇后的纵坐标；
- 实现一个判断函数，用于对给定的结果列表判断是否满足N皇后共存，返回bool值；
- 递归实现一个N皇后求解函数，在已有共存的皇后坐标基础上，增加一个新的皇后纵坐标，且遍历该纵坐标为0~N-1，并逐个调用判断函数，看增加了新皇后之后是否共存：
- 若共存，则在求解中增加该位置值，
- 若此时已经完成了N个皇后的设计，则保存当前结果
- 若完成皇后个数<N，则在此基础上递归调用N皇后求解函数。
- 无论当前是否共存，都将新加入的皇后位置弹出，来寻求新的结果。
- 实现了一个显示N皇后共存结果的函数，打印显示，便于可视化验证。
import copy def judge(queenLocs): """ 判断给定的位置列表下，是否满足皇后共存 :param queenLocs: 1-N个元素，每个元素为该一个皇后的列坐标 :return: True or False """ for queen1, loc1 in enumerate(queenLocs[:-1]): for queen2, loc2 in enumerate(queenLocs[queen1+1:], queen1+1): if loc2 == loc1 or queen2 - queen1 == abs(loc2 - loc1):#位于同列或对角线 return False return True def display(queenLocs): """ 显示皇后位置 :param queenLocs:皇后位置列表 :return: None """ for loc in queenLocs: line = "___"*loc + " * " + "___"*(len(queenLocs)-loc-1) print(line) def solveNqueen(queenNum, queenLocs = [], results = []): """ 利用DPS递归+回溯所有可能的N皇后问题，并返回所有解 :param queenNum: 皇后数目 :param queenLocs: 已有皇后位置，默认为空 :param results: 记录所有解决方案 :return: None """ for loc in range(queenNum): queenLocs.append(loc) #在已有皇后位置的基础上，尝试再放置一个皇后 if judge(queenLocs): #新放入的皇后能够共存 if len(queenLocs) == queenNum: #若已放置目标数量的皇后 results.append(copy.deepcopy(queenLocs)) #记录当前解决方案，并将一份深拷贝加入到结果 else: #未达到目标数量且当前可以共存，在此基础上 solveNqueen(queenNum, queenLocs, results) queenLocs.pop() if __name__ == "__main__": results = [] solveNqueen(8, results = results) print(len(results)) display((results[0]))
