八皇后

Quackity · 2023-08-02 14:24:04 · 个人记录

#include <iostream>
#include <vector> 
using namespace std;
int a[100005];
int n, ans = 0, k;
// now: 当前是第几行 
int chess[20][20];
vector<int> path;
bool check(int x, int y) {//判断是否能落子 
    for (int i = 1; i <= x - 1; i++) {
        if (chess[i][y]) return false;
        if (y - (x - i) >= 1 && chess[i][y - (x - i)]) return false; 
        if (y + (x - i) <= n && chess[i][y + (x - i)]) return false;
    }
    return true;
}
void dfs(int now) {
    if (now == n + 1) {//出口 
        ans++;
        if (ans <= 3) {//改变棋子位置 
            for (int i = 0; i < path.size(); i++) {
                cout << path[i] << ' ';
            }
            cout << endl;
        }       
        return ;
    }
//  for循环i: 1到n (i:放在第i列) {
    for (int i = 1; i <= n; i++) {
//      如果可以放   
//      cout << now << ' ' << i << ' ' << check(now, i) << endl;
        if (check(now, i)) {
//          把棋子放上去
            chess[now][i] = 1;
            path.push_back(i); 
            dfs(now+1);
            chess[now][i] = 0;
            path.pop_back();
        } 
    } 
} 

int main(){
    cin >> n;
    dfs(1);
    cout << ans << endl;

}