[BOJ G4][C++] 백준 9663번: N-Queen

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

9663번: N-Queen

 

문제

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N < 15)

출력

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

 

풀이

좌표를 (r,c) 라고 둔다.

col[x] : x번째 열에 퀸의 여부
increase[x] : i+k=x 인 우상향 대각선에 퀸의 여부
decrease[x] : i-k+(n-1) = x 인 우하향 대각선에 퀸의 여부

(이때 인덱스가 음수가 되는 상황을 방지하기 위해 n-1을 더했다)

 

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>

using namespace std;

int n, ans;
bool col[15];
bool increase[30];
bool decrease[30];

void recur(int r) {
    if(r == n) {
        ans++;
        return;
    }
    
    for(int c=0; c<n; c++) {
        if(col[c] || increase[r+c] || decrease[n+r-c])
            continue;
            
        col[c] = increase[r+c] = decrease[n+r-c] = true;
        recur(r+1);
        col[c] = increase[r+c] = decrease[n+r-c] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    cin >> n;
    
    recur(0);
    
    cout << ans;
    
    return 0;
}

/*
 */