고전 알고리즘 시리즈 n 황후 문제

N 황후 문 제 는 N * N 의 바둑판 에 N 개의 황 후 를 놓 고 줄 마다 서로 공격 하지 못 하 게 하 는 전형 적 인 문제 입 니 다 (같은 줄, 같은 열, 같은 사선 의 황 후 는 자동 으로 공격 합 니 다).
N 황후 문 제 를 푸 는 것 은 알고리즘 에서 역 추적 법 을 응용 한 전형 적 인 사례 이다.
역 추적 알고리즘 도 탐색 법 이 라 고 하 는데 이것 은 문 제 를 체계적으로 검색 하 는 방법 이다.역 추적 알고리즘 의 기본 사상 은 한 길 로 앞으로 가면 들 어 갈 수 있 고 들 어 갈 수 없 으 면 되 돌아 오고 다른 길 로 다시 시도 하 는 것 이다.
      현실 에서 많은 문 제 는 우리 가 그 모든 가능성 을 끝까지 들 어 낸 다음 에 그 중에서 특정한 요 구 를 만족 시 킬 수 있 는 가능성 이나 가장 좋 은 상황 을 찾 아 전체 문 제 를 해결 해 야 한다.역 추적 알고리즘 은 바로 이런 문 제 를 해결 하 는 '통용 알고리즘' 으로 '만능 알고리즘' 이 라 고 불 린 다.N 황후 문 제 는 N 이 커 졌 을 때 이렇게 공간 이 큰 문 제 를 풀 었 기 때문에 이런 방법 으로 풀 기 에 비교적 적합 하 다.이것 도 N 황후 문제 의 전통 적 인 해법 으로 매우 고전적 이다.
      다음은 알고리즘 의 고급 위조 코드 설명 입 니 다. 여 기 는 N * N 의 행렬 로 바둑판 을 저장 합 니 다.
      1) 알고리즘 을 시작 하여 바둑판 을 비우 고 현재 줄 을 첫 줄 로 설정 하고 현재 열 을 첫 번 째 열 로 설정 합 니 다.
      2) 현재 줄 에서 현재 열 에 있 는 위치 에서 조건 만족 여 부 를 판단 한다 (즉, 이 점 을 거 친 줄, 열 과 사선 에 두 황후 가 없다 는 것 을 보증한다). 만족 하지 않 으 면 4 단계 로 넘 어간 다.
      3) 현재 위치 에서 조건 을 만족 시 키 는 경우:
                 현재 위치 에 황 후 를 두 고 현재 줄 이 마지막 줄 이 라면 해 를 기록 합 니 다.
                 현재 줄 이 마지막 줄 이 아니라면 현재 줄 은 다음 줄 로 설정 하고 현재 줄 은 현재 줄 의 첫 번 째 테스트 대기 위치 로 설정 합 니 다.
                 현재 줄 이 마지막 줄 이 라면 현재 열 은 마지막 열 이 아니 라 현재 열 은 다음 열 로 설정 합 니 다.
                 현재 줄 이 마지막 줄 이 라면 현재 열 은 마지막 열 입 니 다. 돌 이 켜 보면 현재 줄 과 아래 각 줄 의 바둑판 을 비 운 다음 에 현재 줄 은 이전 줄 로 설정 하고 현재 열 은 현재 줄 의 다음 측정 위치 로 설정 합 니 다.
                이상 2 단계 로 돌아 가기
      4) 현재 위치 에서 조건 을 만족 시 키 지 못 하 는 경우:
                현재 열 이 마지막 열 이 아니라면 현재 열 을 다음 열 로 설정 하고 두 번 째 단계 로 돌아 갑 니 다.
                현재 열 이 마지막 열 이 라면 돌 이 켜 보면 현재 줄 이 첫 번 째 줄 이 고 알고리즘 이 종료 되 지 않 으 면 현재 줄 과 아래 각 줄 의 바둑판 을 비 운 다음 에 현재 줄 을 이전 줄 로 설정 하고 현재 줄 은 현재 줄 의 다음 측정 위치 로 설정 하여 두 번 째 단계 로 돌아 갑 니 다. 
        알고리즘 의 기본 원 리 는 위 에 있 는 이 모양 이지 만 사용 하 는 데이터 구조 가 다 르 고 특정한 위치 가 조건 을 만족 시 키 는 지 확인 하 는 방법 도 다르다.효율 을 높이 기 위해 서 는 다 중 스 레 드, 다 중 메모리 표시 바둑판 등 여러 가지 최적화 전략 이 있다.
        이 문 제 를 구체 적 으로 해결 할 때 는 몇 가지 작은 문제 로 나 눌 수 있다.먼저 바둑판 에서 두 황후 가 서로 공격 할 수 있 는 지 판단 하 는 것 이다. 처음에 이 문 제 를 접 했 을 때 가장 먼저 생각 나 는 방법 은 바둑판 을 2 차원 배열 로 저장 한 다음 에 i 행 j 열 에 황 후 를 배치 해 야 할 때 문제 에 대한 설명 에 따라 먼저 i 행 에 황후 가 있 는 지 여 부 를 판단 하 는 것 이다. 줄 마다 황후 가 한 명 밖 에 없 기 때문이다.이 판단 도 생략 하고 제 이 열 에 황후 가 있 는 지 판단 할 수 있다. 이것 도 간단 하 다. 마지막 으로 같은 사선 에 황후 가 있 는 지 판단 해 야 한다. 이 방법 에 따라 두 번 판단 해 야 한다. 대각선 방향 과 마이너스 대각선 방향 은 전체적으로 어렵 지 않다.하지만 쓰 고 나 니 멍청 하 다. N 황후 문제 에서 이 함수 의 사용 횟수 가 너무 많아 서 효율 이 떨 어 지고 개인 적 으로 불쾌 하 다.인터넷 에 접속 해 남 의 실현 을 살 펴 보고 깜짝 놀 랐 다. 소 들 은 1 차원 배열 로 바둑판 을 저장 하고 있 었 다. 어느 위치 에서 황후 가 서로 공격 할 수 있 는 지 에 대한 판단 도 간단 했다.구체 적 인 세부 사항 은 다음 과 같다.
        바둑판 을 N 차원 배열 a [N] 로 저장 합 니 다. 배열 에서 i 번 째 요소 의 값 은 i 행 의 황후 위 치 를 대표 합 니 다. 그러면 문제 의 공간 규 모 를 1 차원 O (N) 로 압축 할 수 있 습 니 다. 충돌 여 부 를 판단 할 때 도 간단 합 니 다. 먼저 줄 마다 황후 만 있 고 배열 에서 하나의 요소 의 위 치 를 차지 하면 충돌 이 존재 하지 않 습 니 다. 그 다음은 열 충돌 입 니 다.a [i] 가 현재 황후 의 열 j 와 같 는 지 판단 하면 됩 니 다.사선 충돌 에 대해 관찰 을 통 해 사선 에서 충돌 하 는 모든 황후 의 위 치 는 규칙 적 인 것 을 발견 할 수 있다. 즉, 그들 이 있 는 행렬 이 서로 줄 어 든 절대 치 는 같다 는 것 이다. 즉, |  row – i | = | col – a[i] | 。이렇게 어느 자리 에 황 후 를 놓 을 수 있 을 지 의 문 제 는 이미 해결 되 었 다.
       다음 에 해결 해 야 할 것 은 어떤 방법 으로 모든 N 황후 의 해 를 찾 는 것 입 니까?위 에서 말 했 듯 이 이 문 제 는 소 급 법의 전형 적 인 응용 이기 때문에 소 급 법 으로 이 문 제 를 해결 할 수 있 고 구체 적 으로 실현 하 는 데 도 두 가지 경로 가 있 으 며 재 귀 와 비 재 귀 가 있다.귀속 방법 은 비교적 간단 하 다. 대체적인 사상 은 다음 과 같다.
     void queen(int row)
    {
              if (n == row)      //결 과 를 찾 았 다 면 결 과 를 인쇄 합 니 다.
                    print_result();
              else {
                          for (k = 0 to N) {/
                                  if (can_place(row, k) { 
                                          place(row, k);   //황 후 를 두다
                                         queen(row + 1);  //다음 줄 계속 탐지
                                  }
                         }
             }
    }
        이 방법 은 i 행 을 탐지 한 후 황후 의 위 치 를 놓 을 수 있 는 j 를 찾 으 면 다음 행 을 재 귀적 으로 탐지 하고, 끝나 면 i 행 j + 1 열 을 계속 탐지 하기 때문에 모든 N 황후 의 해 를 찾 을 수 있다.
        그러나 일반적으로 재 귀적 효율 이 떨 어 지 므 로 이 문제 의 비 재 귀적 실현 에 중점 을 두 고 논의 해 보 자.
        재 귀 방법 이 아 닌 중요 한 문제 중 하 나 는 언제 거 슬러 올 라 가 고 어떻게 거 슬러 올 라 가 느 냐 하 는 문제 입 니 다. 절 차 는 먼저 N 행 의 모든 행 을 탐지 하고 이 행 에 황후 가 놓 일 수 있 는 위 치 를 찾 습 니 다. 구체 적 인 방법 은 이 행 의 모든 열 을 탐지 하여 황 후 를 놓 을 수 있 는 지, 가능 하 다 면 이 열 에 황 후 를 놓 고 다음 행 의 황후 위 치 를 계속 탐지 하 는 것 입 니 다. 예 를 들 어만약 에 모든 열 을 탐지 하고 황후 의 열 을 놓 을 수 있 는 열 을 찾 지 못 했다 면 이때 거 슬러 올 라 가서 지난 줄 의 황후 의 위 치 를 한 줄 뒤로 옮 겨 야 한다. 만약 에 지난 줄 의 황후 가 이동 한 후에 도 위 치 를 찾 지 못 하면 특정한 줄 에서 황후 의 위 치 를 찾 거나 첫 줄 로 거 슬러 올 라 가 야 한다. 만약 에 첫 번 째 줄 의 황후 도 황 후 를 놓 을 수 있 는 위 치 를 찾 지 못 한다 면 이미모든 해제 프로그램 종 료 를 찾 습 니 다. 이 줄 이 마지막 줄 이 라면 이 줄 을 탐지 한 후, 황 후 를 배치 할 위 치 를 찾 으 면 결 과 를 찾 아 인쇄 하 는 것 을 설명 합 니 다. 하지만 이 때 는 여기 서 절 차 를 끝 낼 수 없습니다. 왜냐하면 우 리 는 모든 N 황후 문제 의 모든 해 를 찾 아야 하기 때 문 입 니 다. 이 줄 의 황 후 를 제거 하고 현재 황후 열 수 를 두 고 있 는 다음 줄 을 찾 아야 합 니 다.열 은 계속 탐측 한다.
전체 코드 는 다음 과 같 습 니 다:

/**
*     N    
*                
*                
*               
*        ，           ，          
**/

#include 
#include 
#include 

#define QUEEN 8     //     
#define INITIAL -10000   //      

int a[QUEEN];    //        

void init()  //        
{
	int *p;
	for (p = a; p < a + QUEEN; ++p) 
	{
		*p = INITIAL;
	}
} 

int valid(int row, int col)    //   row  col         
{
	int i;
	for (i = 0; i < QUEEN; ++i)   //       
	{
		if (a[i] == col || abs(i - row) == abs(a[i] - col))   //            
			return 0;
	}
	return 1;
} 

void print()    //    N      
{
	int i, j;
	for (i = 0; i < QUEEN; ++i)
	{
		for (j = 0; j < QUEEN; ++j)
		{
			if (a[i] != j)      //a[i]    
				printf("%c ", '.');
			else                //a[i]    i   a[i]       
				printf("%c ", '#');
		}
		printf("
");
	}
	for (i = 0; i < QUEEN; ++i)
		printf("%d ", a[i]);
	printf("
");
	printf("--------------------------------
");
}

void queen()      //N    
{
	int n = 0;
	int i = 0, j = 0;
	while (i < QUEEN)
	{
		while (j < QUEEN)        // i         ，         
		{
			if(valid(i, j))      //         
			{
				a[i] = j;        // i     
				j = 0;           // i       ，              ，     j  ，      0       
				break;
			}
			else
			{
				++j;             //       
			}
		}
		if(a[i] == INITIAL)         // i              
		{
			if (i == 0)             //      ，               ，           ，    
				break;
			else                    //            ，       
			{
				--i;
				j = a[i] + 1;        //              
				a[i] = INITIAL;      //           ，    
				continue;
			}
		}
		if (i == QUEEN - 1)          //             ，        ，    
		{
			printf("answer %d : 
", ++n);
			print();
			//         ，        N        ，           ，                 。
			//_sleep(600);
			j = a[i] + 1;             //                   
			a[i] = INITIAL;           //           
			continue;
		}
		++i;              //            
	}
}

int main(void)
{
	init();
	queen();
	system("pause");
	return 0;
}