N-Queen

문제

N-Queen문제는 유명한 문제이다. 이는 N × N인 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하시오.

---

입력

첫 번째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 12)

---

출력

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

---

힌트

예제 입력

4

예제 출력

2

#include <iostream> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ void NQueen(); int findQueen(int N, int W, int Check1[], int Check2[], int Check3[]); int main(int argc, char** argv) { NQueen(); return 0; } //Check1 X //Check2 대각선 //Check3 대각선 int findQueen(int N, int W, int Check1[], int Check2[], int Check3[]){ int sum = 0; for(int i=1; i<=N; i++){ //모든 행 체크 if(Check1[i]) continue; if(Check2[W+i]) //y=-x+p => y+x continue; if(Check3[W-i+12]) //y=x+p => y-x continue; if(W==N){ return 1; } Check1[i]=1; Check2[W+i]=1; Check3[W-i+12]=1; //현재 셋팅 sum += findQueen(N,W+1,Check1,Check2,Check3); Check1[i]=0; Check2[W+i]=0; Check3[W-i+12]=0; //다시 초기화 } return sum; } void NQueen(){ int N; //1<=N<=12; //FILE *f = fopen("NQueen.txt", "r"); scanf("%d", &N); int Check1[25]; int Check2[25]; int Check3[25]; for(int i=0; i<=24; i++){ Check1[i] = 0; Check2[i] = 0; Check3[i] = 0; } int sum = findQueen(N, 1, Check1, Check2, Check3); printf("%d", sum); }