[笔记][中国大学mooc][程序设计与算法（二）算法基础][递归][用递归代替多重循环] N皇后问题

本文主要是介绍[笔记][中国大学mooc][程序设计与算法（二）算法基础][递归][用递归代替多重循环] N皇后问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

在这里插入图片描述

使用递归取代多重循环的意义

在本次题目中，循环的重数N是随输入而变的，C语言只能显式地实现固定重数地循环，而递归可以隐式地实现可变地循环重数

N皇后问题可以构建递归函数NQueen(int layer)，layer代表了第layer行，而递归函数枚举了该行的所有情况。

N皇后问题的全部解空间是一个完全树，每个节点有N个子树，而有整个树有N层，此模型与N重循环同构

代码

#include <iostream>
#include <cmath> 
using namespace std;
int N;
char iRowQueenPos[100];
//检测(row,line)落子是否与其他皇后有冲突
bool IsRational(int row, int line){for(int cnt=0; cnt<row; cnt++){//横纵向if(iRowQueenPos[cnt] == line) return false;//对角线向if(row-cnt == abs(line-iRowQueenPos[cnt])) return false;}return true;
}
void NQueen(int row){//递归基，row>=N所有皇后已经被放下，所以输出排列if(row>=N){for(int cnt1=0; cnt1<N; cnt1++) cout << iRowQueenPos[cnt1]+1 << ' '; cout << '\n';}//枚举row行的所有情况for(int line=0; line<N; line++) if(IsRational(row,line)) {iRowQueenPos[row]=line; NQueen(row+1);}return;
}
int main(){cin >> N;NQueen(0);return 0;
}