练习:n皇后问题

n皇后问题其实是回溯算法,简单理解就是"逐步尝试,不可行退回上一步,然后更改上一步"

要注意,如果想要得出所有的解,那么最终结果可行依旧要回溯,直到遍历完所有的可能结果

import numpy as np"""
n皇后问题
"""def n_queen(start, map):for i in range(len(map[start])):# 按行遍历map[start][i] = 1if check(map):if start < len(map) - 1:if not n_queen(start + 1, map):map[start][i] = 0else:print(map)# 将已成立的结果打印出来map[start][i] = 0# 重置else:map[start][i] = 0return Falsedef check(map):# 用于判断是否有皇后处于同一行/列/斜线上line1 = set()line2 = set()line3 = set()line4 = set()for i in range(len(map)):for j in range(len(map)):if map[i][j] == 1:if i in line1:return Falseif j in line2:return Falseif i - j in line3:return Falseif i + j in line4:return Falseline1.add(i)line2.add(j)line3.add(i - j)line4.add(i + j)return Trueif __name__ == "__main__":n = 8# 修改n来实现n皇后map = np.zeros([n, n])n_queen(0, map)

可以加一个全局变量用于统计解的个数

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！