指路->旅行商问题
n皇后问题
可以将nn的棋盘看成一个nn的表格,放置皇后Q,且需要满足两个条件
条件1:同行同列不能放置两个或大于两个皇后
条件2:皇后的斜线上不能存在皇后
i,j表示行值,a[i],a[j]表示列值
|a[i]-a[j]| != |i-j|
3.算法描述
全排列算法的实现
使用递归和回溯
函数范围
0<i<len(皇后的个数)
i+1<j<len(皇后的个数)
函数逻辑
通过两层for循环实现,通过定义常量,并在语句块中自增,判断语句块是否被执行,实现对解空间的筛选
per_result = [] def per(lst,s,e): if s == e: per_result.append(list(lst)) else: for i in range(s,e): lst[i],lst[s] = lst[s],lst[i]#试探 per(lst,s+1,e)#递归 lst[i],lst[s] = lst[s],lst[i]#回溯 #剪枝函数 #args:[1,2,3,4] #return true or false def shear(lst): result = 0 for i in range(len(lst)): for j in range(i+1,len(lst)): if(abs(lst[j] - lst[i]) == abs(j-i)): result += 1 if(result > 0): return True else: return False #格式打印函数 def stamp(st): for i in st: for j in range(len(i)): a = ("."*(i[j]-1)+"#"+"."*(len(i)-i[j])) # print(a,"\t","第{}个皇后放在棋盘的第{}列".format(j+1,i[j])) print(a, "\t", "({},{})".format(j + 1, i[j])) print(" ")#负责空行 num = eval(input("请输入皇后的个数:")) lst = [i+1 for i in range(num)] per(lst,0,num) queen_lst = [] for i in per_result: if(shear(i) == False): queen_lst.append(i) stamp(queen_lst) print("共{:d}种可能".format(len(queen_lst)))
4
更多大学课业实验实训可关注公众号回复相关关键词
学艺不精,若有错误还望指点