赞
踩
n皇后问题是指在一个n*n的国际象棋棋盘上放置n个皇后,使得这n个皇后两两均不在同一行、同一列、统一对角线上,求合法的方案数。
每两个皇后不在同一行也不在一列,同时也不在一个对角线上
判断不在同一对角线:
//第row行皇后的列号为temp[row],第pre行皇后的列号为temp[pre]
if abs(row-pre) == abs(temp[row]-temp[pre]) : 则冲突
使用DFS思想
n = int(input()) #皇后数量 temp = [0 for x in range(n)] #暂存皇后 ans = 0 #方案数 def valid(temp,row,col): #验证皇后是否在同一列、同一对角线 for pre in range(row): if (abs(row-pre) == abs(col-temp[pre])) or temp[pre]==col: return 0 #冲突 return 1 def dfs(temp,row): global ans,n if row == n: #走到最后得到合法的方案 ans += 1 #计算方案数+1 return else: for col in range(n): if valid(temp,row,col) == 1: #col可以放皇后 temp[row] = col dfs(temp,row+1) dfs(temp,0) print(ans)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10;
//n为皇后数量,temp暂存当前皇后的摆放位置,ans为方案数
//hashTable为散列数组,标志x是否已经在temp中
int n,temp[maxn],ans = <
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。