DFS 전문

1. N 황후 문제
질문 설명:
n 에 있다×n 칸 의 바둑판 에는 서로 공격 을 받 지 않 는 n 개의 황후 가 놓 여 있다.체스 의 규칙 에 따라 황 후 는 그것 과 같은 줄 이나 같은 줄 또는 같은 사선 에 있 는 바둑 알 을 공격 할 수 있다.n 후 문 제 는 n 과 같다.×n 의 바둑판 에 n 개의 황 후 를 놓 으 면 그 어떠한 황후 도 같은 줄 이나 같은 열 또는 같은 사선 에 놓 을 수 없습니다.
생각:
N 황후 문 제 를 해결 하려 면 이 n 명의 황 후 를 어떻게 두 어야 하 는 지 를 잘 해결 해 야 합 니 다. 모든 황후 와 앞의 모든 황 후 는 같은 줄, 같은 열, 같은 대각선 에 있 으 면 안 됩 니 다. 우 리 는 행 우선 으로 할 수 있 습 니 다. 즉, 황후 의 행 호 는 순서대로 증가 하고 i 번 째 황 후 는 i 번 째 줄 의 어느 열 에 두 어야 하 는 지 만 생각 하기 때문에 i 번 째 황 후 를 두 었 을 때...1 열 에서 판단 할 수 있 으 며, 1 번 째 자리 에 놓 을 수 있다 면 다음 줄 로 넘 어가 다음 황 후 를 놓 을 수 있다.안 되면 다음 열 로... 마지막 열 까지... 마지막 열 도 놓 을 수 없다 면 이때 놓 는 방법 이 잘못 되 었 다 는 뜻 이 고, 이전 황후 가 놓 았 던 다음 열 로 돌아 가 다시 놓 는 것 이다.이것 이 바로 소 급 법의 정수 이다.n 번 째 황후 가 성공 적 으로 방 치 된 후에 실행 가능 한 해 를 얻 었 습 니 다. 이때 다시 이전 황후 로 돌아 가 다음 실행 가능 한 해 를 찾 습 니 다. 그러면 n 황후 문제 의 모든 실행 가능 한 해 를 찾 을 수 있 습 니 다.
코드:

#include
#include
int n;
int sum=0;
int a[20];   //         
int check(int k)
{
    int i;
    for(i=0;i

2. 소수 링 문제 (HDU 1016)
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1016
질문 설명:
하나의 수 n 을 정 하고 1 에서 n 까지 모두 n 개의 자연 수 를 가지 고 이 n 개의 자연 수 를 하나의 링 으로 구성 하 며 링 에 인접 한 두 수의 합 을 소수 로 하여 이런 링 을 구성 할 수 있 는 모든 상황 을 요구한다.
예 를 들 어 n = 8, 조건 을 만족 시 키 는 소수 링 은 다음 과 같다.
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
총 4 가지 가능.
생각:
모든 위치의 수 를 순환 적 으로 옮 겨 다 니 며 매번 1 부터 n 까지 검색 하고 조건 에 맞 으 면 채 워 넣 고 다음 위치의 숫자 를 스 캔 하 며 조건 에 맞지 않 으 면 건 너 뜁 니 다.
코드:

#include 
#include 
int flag[30];    //        ，1  ，0   。
int a[100];      //     
int n;
int check(int x)   //       
{
    int i;
    for(i=2;i