#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>


int N; // 체스판 크기
int col[100]; // 각 퀸의 위치를 저장할 배열
int result = 0; // 가능한 해의 개수

// 퀸이 배치 가능한지 여부를 확인하는 함수
int promising(int i)
{
    int j;
    for (j = 0; j < i; j++)
    {
        // 같은 열에 있거나 대각선에 있는지 확인
        if (col[j] == col[i] || abs(col[j] - col[i]) == (i - j))
            return 0;
    }
    return 1;
}

// 백트래킹을 이용한 N-퀸 문제 해결 함수
void n_queen(int i)
{
    int j;
    if (i == N)
        result += 1;
    else
    {
        for (j = 0; j < N; j++)
        {
            col[i] = j;
            if (promising(i))
                n_queen(i + 1);
        }
    }
}

int main()
{
    N = 10; // 예: 8-퀸 문제
    n_queen(0);
    printf("Total number of solutions: %d\n", result);
    return 0;
}