N 황후 문제 (역 추적 알고리즘 해법)

N 황후 문제
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3464    Accepted Submission(s): 1599
Problem Description
N * N 의 격자 바둑판 에 N 개의 황 후 를 배치 하여 서로 공격 하지 않 게 합 니 다 (즉, 임의의 2 명의 황 후 는 같은 줄 에 있 는 것 을 허락 하지 않 습 니 다. 같은 열 에 있 는 것 도 허락 하지 않 고 바둑판 테두리 와 45 각 이 되 는 사선 에 있 는 것 도 허락 하지 않 습 니 다.
당신 의 임 무 는 주어진 N 에 대해 몇 가지 합 법 적 인 방치 방법 을 구 하 는 것 입 니까?
 
 
Input
모두 몇 줄 이 있 으 며, 각 줄 의 정수 N ≤ 10 은 바둑판 과 황후 의 수량 을 표시 합 니 다.
 
 
Output
모두 몇 줄 이 있 고 줄 마다 정수 가 있 으 며 입력 줄 에 대응 하 는 황후 의 서로 다른 배치 수량 을 나타 낸다.
 
 
Sample Input
8
 
 
Sample Output
92
바둑판 의 각 열 에 황후 가 하나 밖 에 없 기 때문에 i 는 1 차원 벡터 A (a1, a2, a3... an) 로 i 열 황후 가 있 는 행 a [i] 를 표시 할 수 있 습 니 다. 즉, 공간 을 푸 는 모든 노드 에 n 명의 아들 이 있 기 때문에 공간 크기 는 n ^ n 입 니 다. 이것 은 부분 집합 나무 입 니 다.
구속 조건 은 경사 율 과 줄 번호 가 같 으 면 안 된다 는 것 이다.
역 추적 알고리즘 문제 풀이 방향:
1. 주어진 문제 에 대해 문제 의 해결 공간 을 정의 합 니 다 (부분 집합 트 리 또는 배열 트 리)
2. 검색 하기 쉬 운 공간 구 조 를 확인한다.
3. 깊이 우선 방법 으로 공간 을 검색 하고 검색 과정 에서 가지치기 함수 로 잘못된 검색 을 피한다.

#include 
#include  
#include 
using namespace std;

#define NUM 20
int n;
int x[NUM]; 
int sum; 

inline bool Place(int t) 
{ 
	int i; 
	for (i=1; in) 
	{
		sum++;
	}
	else
		for (i=1; i<=n; i++) 
		{
			x[t] = i;
			if (Place(t)) Backtrack(t+1);
		}
} 

int main() 
{ 
	while (cin>>n)
	{
		sum = 0;
		Backtrack(1);
		printf("%d
", sum);
	}
	return 0; 
}