当前位置:   article > 正文

n皇后问题(DFS)_比赛 题库 提交记录 hack! 博客 帮助 好评差评[-5] #58. n皇后问题百度翻译实时翻

比赛 题库 提交记录 hack! 博客 帮助 好评差评[-5] #58. n皇后问题百度翻译实时翻

n皇后问题是指在一个n*n的国际象棋棋盘上放置n个皇后,使得这n个皇后两两均不在同一行、同一列、统一对角线上,求合法的方案数。
五皇后的合法方案
每两个皇后不在同一行也不在一列,同时也不在一个对角线上
判断不在同一对角线:
//第row行皇后的列号为temp[row],第pre行皇后的列号为temp[pre]
if abs(row-pre) == abs(temp[row]-temp[pre]) : 则冲突

使用DFS思想

1. 只求方案数,不需要求解出其中的过程那么我们就不需要进行回溯

python
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)			
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
C++
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10;
//n为皇后数量,temp暂存当前皇后的摆放位置,ans为方案数 
//hashTable为散列数组,标志x是否已经在temp中 
int n,temp[maxn],ans = <
  • 1
  • 2
  • 3
  • 4
  • 5
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/825427
推荐阅读
相关标签
  

闽ICP备14008679号