八皇后問題即指在一個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
****************************************************************/
新聞熱點
疑難解答
圖片精選
