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; 
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

pp 역 추적 알고리즘 컴 퓨 팅 조합 총화 인 스 턴 스 코드

하나의 배열 candidates 와 하나의 목표 수 target 을 지정 하여 candidates 의 모든 숫자 와 target 의 조합 을 찾 습 니 다. candidates 의 모든 숫자 는 조합 에서 한 번 만...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

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

좋은 웹페이지 즐겨찾기