9663번 N-Queen

백트래킹의 유명한 문제이다.

diagnolline_1은 오른쪽 위로 가는 대각선이고

diagnolline_2는 오른쪽 아래로 가는 대각선이다.

https://www.acmicpc.net/problem/9663

이 문제 풀면서 기억해야할 것

1. 32번 째 줄 코드에 diagnolline_2 배열에서 N + y - i인 이유는 y - i가 음수가 나올 수 있기 때문에 N을 더해준 것이다.

2. 

오른쪽 위로 가는 대각선은 (행, 열)에서 행 + 열이 일정한 값을 가진다.

오른쪽 아래로 가는 대각선은 (행, 열)에서 행 - 열의 값이 일정하다.

참고 : http://blockdmask.tistory.com/181

3. 사실 row나 column 배열 중 하나는 없어도 된다. 

4. 30번 째 줄 코드의 i는 x(열) 역할을 한다.

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
bool row[16] = { false, };
bool column[16] = { false, };
bool diagonalline_1[32] = { false, };
bool diagonalline_2[32] = { false, };
 
int N = 0;
 
int result = 0;
 
void BackTracking(int y)
{
    if (y == N)
    {
        ++result;
 
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        if (!row[y] && !column[i] && !diagonalline_1[y + i] && !diagonalline_2[N + y - i])
        {
            row[y] = true;
            column[i] = true;
            diagonalline_1[y + i] = true;
            diagonalline_2[N + y - i] = true;
            
            BackTracking(y + 1);
 
            row[y] = false;
            column[i] = false;
            diagonalline_1[y + i] = false;
            diagonalline_2[N + y - i] = false;
        }
    }
}
 
int main(void)
{
    scanf("%d", &N);
 
    BackTracking(0);
 
    printf("%d\n", result);
 
    return 0;
}