八皇后问题递归c++

八皇后问题是一个著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上。而递归是解决八皇后问题的一种常用方法。下面是C++递归实现代码：

#include <iostream>
#include <cstring>
using namespace std;

int N = 0;
int q[15];//记录皇后放在当行中的对应列，即皇后位置。
int ans = 0;

int available(int x, int y){//判断皇后是否与棋盘产生冲突
for(int i = 0; i < x; i ++)
if(y == q[i] || (x - i) == (y - q[i]) || (x - i) + (y - q[i]) == 0) //判断所在列|主对角线|副对角线上是否已经有其他皇后
return 0;
return 1;
}

void putit(int j) {//在第j行找能放皇后的位置
for(int i = 0; i < N; i ++) {//从0~N遍历这一行的八个空位
if(available(j, i)) {//如果可以放这个位置就记录下第j个皇后的位置
q[j] = i;
if(j == N - 1){ //如果N个皇后全部放满，累加回溯
ans ++;
return;
}
putit(j + 1);//未放满N个，递归下一个
}
}
q[j] = -1;//如果这一行没有可放的位置说明上一行皇后放的位置不行，要为上一个皇后寻找新的可放位置
return ;
}

int main(){
cin >> N;//n皇后问题
memset(q, -1, sizeof(q));//每行置为未遍历状态。
putit(0);//从棋盘(0,0)向右下递归
cout << ans << endl;
return 0;
}