회고 법 및 N 황후 문제

reference: http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741376.html http://www.cnblogs.com/Creator/archive/2011/05/20/2052341.html
1. 무엇이 역 추적 법 입 니까?
『 8195 』 역 추적 법 은 문 제 를 체계적으로 검색 하여 해답 을 푸 는 방법 이다.검색 과정 에서 문제 의 해 를 찾 아 보 세 요. 찾 지 못 하면 한 걸음 물 러 서서 위로 거 슬러 올 라 가세 요.많은 복잡 한 문제 와 대규모 문제 에 대해 서 는 역 추적 법 을 사용 할 수 있다.『 8195 』 역 추적 법의 기본 사상 은 깊이 있 는 우선 검색 전략 에 따라 뿌리 노드 부터 검색 하 는 것 이다. 특정한 노드 에 이 르 렀 을 때 문 제 를 포함 하 는 해 인지 판단 해 야 한다. 포함 되 어 있 으 면 이 노드 에서 계속 검색 하고 포함 되 지 않 으 면 부모 노드 로 거 슬러 올라간다.역 추적 법 으로 문제 의 모든 해 를 구 할 때 는 뿌리 로 거 슬러 올 라 가 야 하고, 뿌리 가 맺 힌 모든 실행 가능 한 자 수 는 모두 수색 되 어야 끝난다.역 추적 법 으로 어떤 해 를 구 할 때 문제 의 해 를 찾 으 면 끝난다.『 8195 』 역 추적 법 에서 자주 사용 하 는 가지치기 함수: (1) 제약 함수: 노드 에서 제약 에 만족 하지 않 는 서브 나 무 를 줄인다.(2) 한계 함수: 가장 잘 풀 리 지 않 는 하위 트 리 를 빼 기
2. 역 추적 법 문제 풀이 의 일반적인 절차

주어진 문제 에 대해 문제 의 해결 공간 을 확인한다

검색 에 적합 한 방법 으로 공간 을 조직한다

깊이 우선 검색 해 공간 활용

검색 과정 에서 가지치기 함수 로 잘못된 검색 을 피 합 니 다.

3. 알고리즘 프레임 워 크

설정 문제 의 해 는 n 차원 벡터 (a1, a2,.................................................................

비 재 귀 역 추적 프레임 워 크

int a[n], i;
   a[n];
i = 1;
while (i > 0(    ) and (     ))//       
{
    if (i > n)
    {
              ，  ；
    }
    else
    {
        a[i]       ；
        while (a[i]               )
        {
            a[i]       ；
        }
        if (a[i]      )
        {
                   ；
            i = i + 1; //       
        }
        else
        {
                     ；  //  
            i = i - 1;
        }
    }
}

재 귀 역 추적 프레임 워 크

int a[n];
try(int i)
{
    if(i>n)
            ;
    else
   {
    for(j =   ; j <=   ; j=j+1)  //   i       
       {
            if(fun(j))                 //            
              {
                 a[i] = j;
               ...                         //     
                 try(i+1);
                      （ a[i]    ）;
              }
              }
          }
 }

4 예: N 황후 문제
N * N 의 바둑판 에 N 개의 황 후 를 놓 아 줄 마다 서로 공격 하지 못 하 게 합 니 다 (같은 줄, 같은 열, 같은 사선 의 황 후 는 자동 으로 공격 합 니 다).

/*  n  x[1:n]  n     。x[i]    i       i   x[i]  */


#include <stdio.h>
#include <math.h>
#include <stdlib.h>

static int n, x[1000];
static long sum;

/*    k       x[k]               ：  2           （i,j） （k,l）,   i-j = k -l   i+j = k+l，    2          。 */

void OutPut()
{
    for (int i = 1; i <= n; ++i)
        printf("(%d, %d) ", i, x[i]);
    printf("
");
}

int Place(int k)
{
    for (int j = 1; j < k; ++j)
        if (abs(k - j) == abs(x[k] - x[j]) || x[j] == x[k])
            return 0;
    return 1;
}

void BackTrack1(int t)
{
    //  t>n          
    if (t > n)
    {
        sum++;
        OutPut();
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            x[t] = i;
            if (Place(t))                   //    i   ，     
                BackTrack1(t + 1);
        }
    }
}

void BackTrack()
{
    int k;
    x[1] = 0;       //    0
    k = 1;
    while (k >= 1)  //  
    {
        x[k] += 1;  //        
        while ((x[k] <= n) && !(Place(k)))  //     
            x[k] += 1;                      //       
        if (x[k] <= n)                      //    
        {
            if (k == n)                     //       n   
            {
                sum++;                      //    ，  
                OutPut();
            }
            else                            //     ， k  ，       
            {
                k++;
                x[k] = 0;
            }
        }                                   //x[k] > n，          
        else
            k--;                            //    ，   k-1 
    }
}

int main()
{
    clock_t start, finish;
    double duration;

    int nn;
    while (scanf_s("%d", &nn) != EOF)
    {
        n = nn;
        sum = 0;
        for (int i = 0; i <= n; ++i)
            x[i] = 0;
        BackTrack();
        //BackTrack1(1);
        printf("%d
", sum);
    }

    return 0;
}