今天在学习python的时候遇到了很有名的八皇后谜题，题目要求将八个皇后放在棋盘上，而不让她们彼此攻击对方（即没有两个皇后在同一行、同一列或同一对角线上），解决这个问题最经典的方法就是使用回溯法，此处我也使用回溯法编写代码并输出全部摆法（92种），摆法输出形式如下（Q表示皇后）： 回溯法也叫试探法，通过探索不同的选择达到目标，当探索到某一步发现当前选择并不优或者达不到目标，则退回一步重新选择。在用回溯法解决八皇后问题的时候，我使用一维列表存储各个皇后的位置，列表下标表示某一列，列表中存储的数字表示该列皇后摆放的行数，列如queen[i]=j就表示在第i列第j行放置了一个皇后。具体代码如下，详细解释可见注释：
#八皇后（回溯法求解） count = 0 #全局变量count统计共有多少种方法 def isLegal(queen , currentRow): #isLegal函数判断在当前列皇后是否可以放在第currentRow行 for i in range(len(queen)): if queen[i] == currentRow: #判断当前行是否已有皇后 return False rowDiff = abs(queen[i] - currentRow) colDiff = abs(i - len(queen)) if rowDiff == colDiff: #判断当前列当前行的对角线上是否已有皇后 return False return True #若当前行放置皇后合法，则返回True值 def eightQueen(queen , currenCol): global count #全局变量count for i in range(8): #不断尝试当前列第i行是否可以摆放皇后以输出所有摆法 if isLegal(queen , i): queen.append(i) #若当前摆法合理，则将摆法加入列表 if currenCol != 7: #若当前列不是最后一列，则继续探索下一列摆法 eightQueen(queen , currenCol+1) else: #若当前列为第七列（最后一列），则一种新摆法已经探索完毕 count += 1 #count加一，并显示当前摆法 print(count) for m in range(8): #这个嵌套for循环显示本次探索的摆法 for j in range(8): if queen[j] == m: print("|Q" , end='') else: print("| " , end='') print("|") queen.pop() #由于python的特性，函数操作的其实是同一列表对象，故本循环结束后需要将列表最后一个元素pop出去再添加新的元素 def main(): queen = [] currenCol = 0 eightQueen(queen , currenCol) print("总共有" , count , "种摆法") main()在以上代码中，不断探索每一列的皇后放置的行数，若当前行不能放置则回溯一步重新选择行数，若探索到一种解法则返回到第一步开始进行下一种摆法的探索。还可事先指定列表大小，使用下标对表中元素进行更改，这样可以省略每个循环结束后pop的一步，代码如下：
#八皇后（回溯法）2.0版 count = 0 def isLegal(queen , currentRow , currentCol): for i in range(currentCol): if queen[i] == currentRow: return False row = abs(queen[i] - currentRow) col = abs(i - currentCol) if row == col: return False return True def eightQueen(queen , currentCol): global count for i in range(8): if isLegal(queen , i , currentCol): queen[currentCol] = i if currentCol != 7: eightQueen(queen , currentCol+1) else: count += 1 print(count) for m in range(8): for j in range(8): if queen[j] == m: print("|Q" , end='') else: print("| " , end='') print("|") def main(): queen = 8*[-1] currentCol = 0 eightQueen(queen , currentCol) print("共有",count,"种摆法") main()此文仅做学习记录，也欢迎讨论与指正，说白了代码就是在不断的分享与互相切磋中才能流传下去，故若能博君一笑，不胜荣幸，若有帮助，吾亦感开怀。
