반군∥

체스에서 Queen은 가로, 세로, 대각선 방향으로 어느 곳이나 한 번에 움직일 수 있습니다.

x				x
	x			x			x
		x		x		x
			x	x	x
x	x	x	x	Q	x	x	x
			x	x	x
		x		x		x
	x			x			x

위 표에서 Q에 Queen이 있을 때 x가 Queen이 이동할 수 있는 곳입니다.

N을 입력했을 때, N*N 크기의 체스판에 N개의 Queen을 놓을 때 Queen들이 서로 영향을 줄 수 없는 경우의 수를 출력하는 문제입니다.
N=4일 때 가능한 모든 예를 보겠습니다.

	Q
			Q
Q
		Q



		Q
Q
			Q
	Q

▶입력형식 (nqueen.in)
 N (1≤N≤13)
▶출력형식 (nqueen.out)
 N*N의 체스판에서 N개의 Queen들이 서로 영향을 주지 않는 위치로 놓는 방법의 수
▶입력 예
 4
▶출력 예
 2

#include <fstream.h>

ofstream out ("nqueen.out");
ifstream in ("nqueen.in");

int n,num=0,map[13];

void find(int x);
int promising(int x);
void main(){
    in>>n;
    int i;
    for(i=0;i<n;i++){
        map[0]=i;
        find(0);
    }
    out<<num;
}
void find(int x){
    int i;
    x++;
    for(i=0;i<n;i++){
        map[x]=i;
        if(promising(x)){
            if(x==n-1) num++;
            else find(x);
        }
    }
}
int promising(int x){
    int i;
    for(i=0;i<x;i++){
        if(map[x]==map[i]||map[x]-map[i]==x-i||map[x]-map[i]==i-x) return 0;
    }
    return 1;
}