八皇后問題的相關C++代碼解答示例

更新時間：2015年08月15日 11:03:38 作者：低調(diào)小一

這篇文章主要介紹了八皇后問題的相關C++代碼解答示例,文中包括ACM競賽的八皇后相關知識的練習實例,需要的朋友可以參考下

八皇后問題即指在一個8*8的棋盤上放置8個皇后，不允許任何兩個皇后在棋盤的同一行、同一列和同一對角線上。關鍵字：遞歸、上溯.通用技巧：
經(jīng)觀察發(fā)現(xiàn)，對8 x 8的二維數(shù)組上的某點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
因此可設兩個數(shù)組b[15],c[15]分別表示主、從對角線是否安全
（為1表示有皇后，不安全；為0表示安全）

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

題目描述：
會下國際象棋的人都很清楚：皇后可以在橫、豎、斜線上不限步數(shù)地吃掉其他棋子。如何將8個皇后放在棋盤上（有8 * 8個方格），使它們誰也不能被吃掉！這就是著名的八皇后問題。
對于某個滿足要求的8皇后的擺放方法，定義一個皇后串a(chǎn)與之對應，即a=b1b2...b8，其中bi為相應擺法中第i行皇后所處的列數(shù)。已經(jīng)知道8皇后問題一共有92組解（即92個不同的皇后串）。
給出一個數(shù)b，要求輸出第b個串。串的比較是這樣的：皇后串x置于皇后串y之前，當且僅當將x視為整數(shù)時比y小。
輸入：
第1行是測試數(shù)據(jù)的組數(shù)n，后面跟著n行輸入。每組測試數(shù)據(jù)占1行，包括一個正整數(shù)b(1 <= b <= 92)
輸出：
輸出有n行，每行輸出對應一個輸入。輸出應是一個正整數(shù)，是對應于b的皇后串。
樣例輸入：
2
1
92
樣例輸出：
15863724
84136275

思路
先貼出一個可以ac的擺放位置出來，防止大家連國際象棋棋盤的樣子都不清楚。

2015815110349401.png (395×269)

由于八個皇后不能處在同一行，那么可以肯定每個皇后占據(jù)一行。我們可以先定義一個數(shù)組column[9],數(shù)組中的第i個數(shù)字表示位于第i行皇后的列號(因為數(shù)組下標從0開始，因此這里想表示1-8需要申請9個整型的數(shù)據(jù)空間)。
先把column數(shù)組初始化為1-8,忽略開始的第一個元素
接下來，對column做無重復的全排列，因為我們使用不同的數(shù)字對column進行初始化，所以八皇后肯定在不同的列。
接下來，我們只需要判斷八皇后是否在同一對角線即可，學過數(shù)學的都知道，可以表示為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:預處理八皇后的下標數(shù)組
 */
void pre_prosess(int n)
{
  int i;
 
  for (i = 1; i <= n; i ++) {
    column[i] = i;
  }
}
 
/**
 * Description:column數(shù)組數(shù)字交換
 */
void swap(int begin, int k)
{
  int temp;
 
  temp = column[begin];
  column[begin] = column[k];
  column[k] = temp;
}
 
/**
 * Description:防止全排列出現(xiàn)重復數(shù)據(jù)
 */
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
****************************************************************/

您可能感興趣的文章: