N个皇后（递归）

N皇后问题
输入一个正整数N，则程序输出N皇后问题的全部摆法。
输出结果里的每一行都代表一种摆法。行里的第i个数字如果是n，就代表第i行的皇后应该放在第n列。
皇后的行、列编号都是从1开始算。
样例输入:
4
样例输出:
2413
3142

嘿嘿๑乛◡乛๑
先说一下递归的作用:
1.替代多重循环
2.解决本来就是递归形式定义的问题
3.将问题分解为规模更小的子问题进行求解

而这里8个皇后就是用来递归代替多重循环
从第0行开始摆放，如果该方案没有冲突，则继续摆放下一行，递归结束标志是N行全部摆完，输出其中一个结果。

#include <iostream>
#include <cmath>

using namespace std;

int N;
int queenPos[100];


void NQueen(int k);

int main()
{
    cin>>N;
    NQueen(0);//从第0行开始摆放皇后
    return 0;
}

void NQueen(int k)
{
    if(k==N) //N个皇后已经摆好
    {
        for(int i=0; i<N; i++)
            cout<<queenPos[i]+1<<" ";
        cout<<endl;
        return;
    }

    int i,j;
    for(i=0; i<N; i++) //尝试当前行的每一列，看是否能放置皇后
    {
        for(j=0; j<k; j++) //和已摆好的k个皇后进行比较
        {
            /*
            1皇后在同一列，即  queePos[j]==i
            2皇后在对角线上，则 行的差的绝对值=列的差的绝对值 即 abs(k-j)==abs(queenPos[j]-i)
            */
            if(queenPos[j]==i || abs(k-j)==abs(queenPos[j]-i))
                break;// 冲突，测试下一个位置
        }

        if(j==k) //上一个循环没有执行break,当前位置i不冲突
        {
            queenPos[k]=i; // 记录下第k个皇后摆放位置i
            NQueen(k+1);
        }
    }
}

N个皇后 （递归）

N个皇后（递归）