n皇后问题

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

典型的回溯法问题

思路：

尝试性的放置 ，从第一行开始，接着在下一行放置，（这里的好处就是不需要考虑行了，只需要考虑列和对角线）

一直纠结第一行的问题，代码中直接传参数为0，一直好奇如何控制第一行的列的变化，后来将0自己模拟走了一遍才明白。

注意判断的是否符合规则的公式：（列==列）（abs（列-列）==abs（行-行））

具体细节见注释（仔细阅读，一定能看懂，）

#include<iostream>

#include <math.h>

#define N 8

using namespace std;


int num=0;//用来记录总的放置个数

int cur[8];//此全局变量是用来记录第i行放在得第j列，其中下标为i，值为j

int check(int n){//传进来行

    for(int i=0;i<n;i++){

        if(cur[i]==cur[n]||abs(n-i)==abs(cur[n]-cur[i])){//判断当前放置的位置是否与之前的放置位置是否在同一列或同斜列

            return 0;

        }

    }

    return 1;

}

void putQueen(int n){

    if(n==N){//如果找到了最后一行的下一行，那么就可以将次数+1了(就是之前把所有的行已经放完了，数组下标从0开始的勿忘)

        num++;

    }else{

        for(int j=0;j<N;j++){//列的位置从0往最后放置

            cur[n]=j;//记录下当前行的当前列

            if(check(n)){//判断当前放置的行列是否合适

                putQueen(n+1);//开始进行下一行的放置

            }

        }

    }


}

int main(){

    putQueen(0);

    cout<<num;

    return 0;

}