C 언어 는 역 추적 알고리즘 을 바탕 으로 8 황후 문 제 를 해결 하 는 방법

본 고 는 C 언어 가 역 추적 알고리즘 을 바탕 으로 8 황후 문 제 를 해결 하 는 방법 을 실례 로 서술 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
질문 설명:
8 황후 문 제 는 오래 되 고 유명한 문제 로 역 추적 알고리즘 의 전형 적 인 사례 이다.8X8 칸 의 체스 판 에 8 개의 황 후 를 배치 하여 서로 공격 하지 못 하 게 하 는 것 이다.즉,임 의 두 황 후 는 같은 줄,같은 열 또는 같은 사선 에 있 지 못 하고 몇 가지 방법 이 있 는 지 물 었 다.
문제 풀이:
역 추적 알고리즘 을 사용 합 니 다.즉,첫 줄 부터 차례대로 황후 의 위 치 를 탐색 하고 찾 으 면 황 후 를 두 고 다음 줄 을 탐색 합 니 다.이 줄 에 황 후 를 놓 을 위치 가 없다 면 이전 줄 로 거 슬러 올 라 가 황 후 를 놓 을 수 있 는 정 보 를 제거 하고 이 줄 에 황 후 를 놓 을 수 있 는 다음 위치 부터 황후 의 위 치 를 알 아 보 자.모든 해 를 구 할 때 한 조 의 해 를 찾 을 때마다 이 조 의 마지막 황후 의 위치 정 보 를 제거 하고 이 행 의 다른 하 나 를 황후 의 위 치 를 탐색 하여 차례대로 거 슬러 올 라 가 해 를 구한다.
메모리 구조:
1 차원 배열:col[8]:제 i 열 에 황후 의 표시 가 있 는 지 없 는 지 저장 합 니 다.
1 차원 배열:left[15]:왼쪽 사선 마다 황후 의 표시 가 있 는 지 없 는 지 저장 합 니 다.
1 차원 배열:right[15]:모든 오른쪽 직선 에 황후 의 표시 가 있 는 지 없 는 지 저장 합 니 다.
1 차원 배열:Q[8]:제 i 행 을 저장 하 는 황후 의 열 아래 표 시 됩 니 다.
코드 구현:

#include<stdio.h>
#define N 8
int col[N] = { 0 };
int right[2 * N - 1] = { 0 };
int left[2 * N - 1] = { 0 };
int Q[N];
int cnt = 0;
void Print()
{
  int i;
  for (i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
    {
      if (Q[i] == j)
        printf("■");
      else
        printf("□");
    }
    printf("
");
  }
  printf("==========================
");
  cnt++;
}
void Queen(int i)
{
  int j;
  for (j = 0; j < N; j++)
  {
    if ((!col[j]) && (!left[i + j]) && (!right[7 + i - j]))
    {
      Q[i] = j;//   
      col[j] = 1;
      left[i + j] = 1;
      right[N - 1 + i - j] = 1;//       
      if (i < N - 1)
      {
        Queen(i + 1);
      }
      else
      {
        Print();
      }
      col[j] = 0;
      right[N - 1 + i - j] = 0;
      left[i + j] = 0;//    ，      
    }
  }
}
int main(void)
{
  Queen(0);
  printf("%d", cnt);
  getchar();
  return 0;
}

실행 결과:
모두 92 조 가 풀 었 고 앞의 결 과 는 생략 했다.

본 고 에서 말 한 것 이 여러분 의 C 언어 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.