queens

/*
 Author: Cao Beijian
 Result: AC Submission_id: 4270941
 Created at: Sun Apr 03 2022 12:06:29 GMT+0800 (China Standard Time)
 Problem_id: 5439   Time: 4 Memory: 1732
*/

#include <stdio.h>
int chessboard[25] = { 0 };
int count = 0;
int rows;
char check(int k, int col){
    int i = 1;
    for(i = 1;i < k;i++){
        if(chessboard[i] == col || abs(i - k) == abs(chessboard[i] - col)){
            return 0;
        }
    }
    return 1;
}
void dfs(int k){
    if(k > rows){
        count++;
        //output();
        return;
    }
    else{
        int j;
        for(j = 1;j <= rows;j++){
            if(check(k, j)){
                chessboard[k] = j;
                dfs(k + 1);
            }
            chessboard[k] = 0;
        }
    }
}
int main(){
    scanf("%d", &rows);
    dfs(1);
    printf("%d\n", count);
    return 0;
}