8 황후 문제 에 대한 C+코드 해답 예시

8 황후 문 제 는 8*8 의 바둑판 에 8 개의 황 후 를 놓 고 두 황후 가 바둑판 의 같은 줄,같은 열 과 같은 대각선 에 있 는 것 을 허락 하지 않 는 다 는 것 을 말한다.키워드:재 귀,역 추적,통용 기법:
관찰 결과 8 x 8 의 2 차원 배열 의 특정한 점 a[i][j](0<=i,j<=7)
그 주 대각선(즉 왼쪽 위 에서 오른쪽 아래)위의 모든 점 의 i-j+7 의 값(범 위 는(0,14)과 같다.
대각선(즉,오른쪽 위 에서 왼쪽 아래)의 모든 점 의 i+j 의 값(범 위 는(0,14)과 같다.
또한 각 주 대각선 간 의 i-j+7 의 값 이 다 르 고 대각선 간 의 i-j+7 의 값 도 다르다.
예 를 들 어 a[3][4]:
주:3-4+7=6
부터:3+4=7
따라서 두 개의 배열 b[15]를 설정 할 수 있 고 c[15]는 각각 주,대각선 에서 안전 한 지 여 부 를 나타 낸다.
(1 은 황후 가 있 고 안전 하지 않다 는 뜻 이다.안전
줄 마다 황후 가 하나 있 습 니 다.
각 i 황후 가 각 i 줄 에 놓 기(0<=i<=7)
void eightQueens( int line );
제목 설명: 
체스 를 할 줄 아 는 사람들 은 황 후 는 가로,세로,사선 에서 걸음 수 를 제한 하지 않 고 다른 바둑 알 을 먹 을 수 있다 는 것 을 잘 알 고 있다.어떻게 8 개의 황 후 를 바둑판 위 에 놓 습 니까?이것 이 바로 유명한 8 황후 문제 다.  
요 구 를 만족 시 키 는 8 황후 의 배치 방법 에 대해 황후 꼬치 a 와 이에 대응 하 는 것 을 정의 한다.즉,a=b1b 2.b8 이다.그 중에서 bi 는 해당 하 는 배열 법 에서 i 행 황후 가 처 한 열 이다.8 황후 문 제 는 모두 92 팀 으로 알 고 있 습 니 다. 
b 번 째 문자열 을 출력 하 라 고 숫자 b 를 제시 합 니 다.꼬치 의 비 교 는 다음 과 같다.황후 꼬치 x 는 황후 꼬치 y 앞 에 두 고 x 를 정수 로 볼 때 y 보다 작다. 
입력: 
첫 번 째 줄 은 테스트 데이터 의 그룹 수 n 이 고 뒤에 n 줄 을 따라 입력 합 니 다.각 조 의 테스트 데 이 터 는 1 줄 을 차지 하 며,하나의 정수 b(1<=b<=92)를 포함한다. 
출력: 
출력 은 n 줄 이 있 고 각 줄 의 출력 은 하나의 입력 에 대응 합 니 다.출력 은 정수 이 고 b 에 대응 하 는 황후 꼬치 입 니 다. 
샘플 입력: 
2 
1 
92 
샘플 출력: 
15863724 
84136275 
사고의 방향
먼저 ac 가 가능 한 위 치 를 붙 여 체스 판 의 모습 도 모 르 게 합 니 다.

8 명의 황후 가 같은 줄 에 있 을 수 없 기 때문에 모든 황후 가 한 줄 을 차지 할 것 이 라 고 확신 할 수 있다.우 리 는 먼저 배열 column[9]을 정의 할 수 있 습 니 다.배열 의 i 번 째 숫자 는 i 행 황후 에 있 는 열 번 호 를 표시 합 니 다.
먼저 column 배열 을 1-8 로 초기 화하 고 시작 하 는 첫 번 째 요 소 를 무시 합 니 다.
그 다음 에 column 에 대해 반복 되 지 않 는 모든 배열 을 합 니 다.우 리 는 서로 다른 숫자 로 column 을 초기 화 하기 때문에 8 황 후 는 반드시 다른 열 에 있 을 것 입 니 다.
그 다음 에 우 리 는 8 황후 가 같은 대각선 에 있 는 지 판단 하면 됩 니 다.수학 을 배 운 사람 은 모두 알 고 있 습 니 다.Y=x+b 또는 y=-x+b 라 고 할 수 있 습 니 다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define EIGHT 8
 
struct result
{
  int total;
  int num[10];
};
 
int wzyindex, column[10];
struct result results[100];
 
/**
 * Description:           
 */
void pre_prosess(int n)
{
  int i;
 
  for (i = 1; i <= n; i ++) {
    column[i] = i;
  }
}
 
/**
 * Description:column      
 */
void swap(int begin, int k)
{
  int temp;
 
  temp = column[begin];
  column[begin] = column[k];
  column[k] = temp;
}
 
/**
 * Description:           
 */
int check_swap(int begin, int k)
{
  int i;
  for (i = begin; i < k; i ++) {
    if (column[i] == column[k]) {
      return 0;
    }
  }
  return 1;
}
 
int is_eightqueue(int n)
{
  int i, j;
  for (i = 1; i <= n; i ++) {
    for (j = i + 1; j <= n; j ++) {
      if (i - j == column[i] - column[j] || i - j == column[j] - column[i])
        return 0;
    }
  }
  return 1;
}
 
void permutation_queue(int begin, int end)
{
  int k, total;
  if (begin == end) { //           
    if (is_eightqueue(end)) {
      for (k = 1, total = 0; k <= end; k ++) {
        total = 10 * total + column[k];
        results[wzyindex].num[k] = column[k]; 
      }
      results[wzyindex].total = total;
      wzyindex ++;
    }
  } else {  //    
    for (k = begin; k <= end; k ++) {
      if (check_swap(begin, k)) { //          
        swap(begin, k);
        permutation_queue(begin + 1, end);
        swap(begin, k);
      }  
    }
  }
}
 
int compare(const void *p, const void *q)
{
  const struct result *a = p;
  const struct result *b = q;
 
  return a->total - b->total;
}
 
int main()
{
  int i, n, m;
  pre_prosess(EIGHT);
  wzyindex = 0;
  permutation_queue(1, EIGHT);
  qsort(results, wzyindex, sizeof(results[0]), compare);
  while (scanf("%d", &n) != EOF) {
    while (n --) {
      scanf("%d", &m);
      m -= 1;
      for (i = 1; i <= EIGHT; i ++) {
        printf("%d", results[m].num[i]);
      }
      printf("
");
    }
  }
 
  return 0;
}

/**************************************************************
    Problem: 1140
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:916 kb
****************************************************************/
생각
사실은 dfs 가 여러 겹 으로 옮 겨 다 니 며 요구 에 부합 되 는 모든 조합 을 찾 아 ac 코드 에 직접 올 라 가 는 것 입 니 다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
 
#define N 8
 
typedef struct point {
  int x, y;
} point;
point pts[N];
 
typedef struct string {
  char str[N + 1];
} string;
string strs[93];
 
int windex, count;
 
int isOk(int x, int y)
{
  int i, flag = 1;
 
  for (i = 0; i < count; i ++) {
    if (pts[i].y == y || abs(y - pts[i].y) == abs(x - pts[i].x)) {
      flag = 0;
      break;
    }
  }
 
  return flag;
}
 
void bfsEight(int level)
{
  int i;
 
  if (level > N) {
    for (i = 0; i < N; i ++) {
      strs[windex].str[i] = pts[i].y + '0';
    }
    strs[windex].str[i] = '\0';
    windex ++;
  } else {
    point t;
    for (i = 1; i <= N; i ++) {
      t.x = level;
      t.y = i;
 
      if (isOk(t.x, t.y)) {
        pts[count ++] = t;
        bfsEight(level + 1);
        count -= 1;
      }
    }
  }
}
 
int cmp(const void *p, const void *q)
{
  const string *a = p;
  const string *b = q;
 
  return strcmp(a->str, b->str);
}
 
int main(void)
{
  int n, num;
 
  count = windex = 0;
 
  bfsEight(1);
  qsort(strs, count, sizeof(strs[0]), cmp);
 
  scanf("%d", &n);
 
  while (n --) {
    scanf("%d", &num);
 
    printf("%s
", strs[num - 1].str);
  }
 
  return 0;
}

/**************************************************************
    Problem: 1140
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:916 kb
****************************************************************/