[알고리즘] c++ cpp N-Queen

포인트

1. 판을 만들면서 유망성을 확인한다. (백트랙킹)

2. 퀸은 가로, 세로, 대각선을 모두 갈 수 있는 말?

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#include <iostream>

using namespace std;
// 전역 변수 잘 사용하기
int n, answer;
int col[16];

//배치 가능 여부
bool promising(int a) {
    int temp = 1;
    bool flag = true;

    while (temp < a && flag) {
        //같은 열이거나 대각선이라면 배치 못함
        if (col[a] == col[temp] || abs(col[a] - col[temp]) == a - temp)
            flag = false;
        temp+=1;
    }

    return flag;
}

void n_queen(int i) {
    if (promising(i)) //==true 를 사용해도 된다.
    {
        //판 완성
        if (i == n) answer+=1;

        else{
            for (int j = 1; j <= n; j++) {
                col[i + 1] = j;
                n_queen(i + 1); //재귀 적으로 (백 트랙킹)
            }
        }
    }
}

int main() {
    cin >> n;
    n_queen(0);

    cout << answer << '\n';
}