八皇後成績的相干C++代碼解答示例

八皇後成績的相干C++代碼解答示例。本站提示廣大學習愛好者：（八皇後成績的相干C++代碼解答示例）文章只能為提供參考，不一定能成為您想要的結果。以下是八皇後成績的相干C++代碼解答示例正文

八皇後成績即指在一個8*8的棋盤上放置8個皇後，不許可任何兩個皇後在棋盤的統一行、統一列和統一對角線上。症結字：遞歸、上溯.通用技能：
經不雅察發明，對8 x 8的二維數組上的某點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表現有皇後，不平安；為0表現平安）

每行有且唯一一個皇後：
每i個皇後放在每i行(0<=i<=7)
void eightQueens( int line );

標題描寫： 
會下國際象棋的人都很清晰：皇後可以在橫、豎、斜線上不限步數地吃失落其他棋子。若何將8個皇後放在棋盤上（有8 * 8個方格），使它們誰也不克不及被吃失落！這就是有名的八皇後成績。  
關於某個知足請求的8皇後的擺放辦法，界說一個皇後串a與之對應，即a=b1b2...b8，個中bi為響應擺法中第i行皇後所處的列數。曾經曉得8皇後成績一共有92組解（即92個分歧的皇後串）。 
給出一個數b，請求輸入第b個串。串的比擬是如許的：皇後串x置於皇後串y之前，當且僅當將x視為整數時比y小。 
輸出： 
第1行是測試數據的組數n，前面隨著n行輸出。每組測試數據占1行，包含一個正整數b(1 <= b <= 92) 
輸入： 
輸入有n行，每行輸入對應一個輸出。輸入應是一個正整數，是對應於b的皇後串。 
樣例輸出： 
2 
1 
92 
樣例輸入： 
15863724 
84136275 

思緒
先貼出一個可以ac的擺放地位出來，避免年夜家連國際象棋棋盤的模樣都不清晰。

因為八個皇後不克不及處在統一行，那末可以確定每一個皇後占領一行。我們可以先界說一個數組column[9],數組中的第i個數字表現位於第i行皇後的列號(由於數組下標從0開端，是以這裡想表現1-8須要請求9個整型的數據空間)。
先把column數組初始化為1-8,疏忽開端的第一個元素
接上去，對column做無反復的全分列，由於我們應用分歧的數字對column停止初始化，所以八皇後確定在分歧的列。
接上去，我們只須要斷定八皇後能否在統一對角線便可，學過數學的都曉得，可以表現為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("\n");
    }
  }
 
  return 0;
}

/**************************************************************
    Problem: 1140
    User: wangzhengyi
    Language: C
    Result: Accepted
    Time:10 ms
    Memory:916 kb
****************************************************************/
dfs思緒
其實就是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\n", strs[num - 1].str);
  }
 
  return 0;
}

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