HDU2553 N皇后（回溯）

题目链接

N 皇后问题

题解：首先应该意识到，在棋盘（二维数组）中，同一条主对角线（左上到右下）上的点的 y-x 值相等，同一条副对角线（右上到左下）上的点的 x+y 值相等。用二维数组 vis 判断当前尝试的皇后所在列和两个对角线是否已存在其他皇后。主对角线 y-x 可能为负，加 n 即可。

void search(int cur){  //当前行
    if(cur == n){
        ans++;
        return;
    }
    for(int i = 0; i < n; i++){
        if(!vis[0][i] && !vis[1][cur+i] && !vis[2][cur-i+n]){ //分别代表列、副对角线、主对角线
            //C[cur] = i;       若不需打印解 可忽略C数组
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 1;
            search(cur+1);
            vis[0][i] = vis[1][cur+i] = vis[2][cur-i+n] = 0;
        }
    }
}

HDU 这题直接交会超时，可能有重复数据，因为只有 10 个数，把答案打表一下就行了。

#include <iostream>
using namespace std;
int n=1,x[11]={0,1,0,0,2,10,4,40,92,352,724};
int main(){
    while(n!=0){
        cin >> n;
        if(n!=0) cout << x[n] << endl;
    }
    return 0;
}