[백트래킹] BOJ 9663 N-Queen

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

9663번: N-Queen

 

문제 해결 알고리즘

 

대표적인 백트래킹 문제

 

아래의 링크에 푸는 방법이 있습니다.

https://kimmessi.tistory.com/86?category=871925 

[알고리즘] 백트래킹 - n-Queens, 해밀턴회로

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int N, cnt;
int col[16];

bool promising(int i){
  int k = 1;
  bool flag = true;

  while(k<i && flag){
    if(col[i] == col[k] || abs(col[i] - col[k]) == i-k) flag = false;
    k++;
  }
  return flag;
}

void queens(int i){

  if(promising(i)){

    if(i == N) cnt++;
    else {
      for(int j=1;j<=N;j++){
        col[i+1] = j;
        queens(i+1);
      }
    }
  }
}

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> N;

  queens(0);
  cout << cnt;
}