백준 9663번 문제 ( N - Queen )

문제 출처 : https://www.acmicpc.net/problem/9663

9663번: N-Queen

이번 문제는 백트래킹의 전형적인 예시인 N-Queen 문제이다.

이 문제는 퀸이 서로 공격할 수 없게 놓는 총 경우의 수를 출력하는 문제이다.

완벽하게 백트래킹이라는 기법을 이해는 못하였지만 점차 문제를 풀면서 개념을 확립할 예정이다.

아래는 해당 문제를 해결한 소스이다.

#include<stdio.h>
#pragma warning(disable:4996)
int chess[16];
int count;
int flag;
void BackTracking(int row, int N)
{
    if (row == N)
    {
        count++;
        return;
    }
    else
    {
        for (int i = 0; i < N; i++)
        {
            flag = 0;
            chess[row] = i;
            for (int j = 0; j < row; j++)
            {
                int num = chess[row] - chess[j];
                if (num < 0)
                    num = num * -1; // 대각선 체크 
                if(chess[row] == chess[j] || (row - j) == num) // 세로, 대각선 체크
                    flag = 1;
            }
            if (flag == 0)
                BackTracking(row + 1, N);
        }
    }
}
int main()
{
    int N;
    scanf("%d", &N);
    BackTracking(0,N);
    printf("%d", count);
}