今天寫點簡單的，C 語言求解八皇后問題，相信學過 C 語言的朋友一定知道這個經典問題吧，解法也是多種，目前主要有回溯，遞推兩種方法，今天講回溯 + 遞歸的求法，效率可能不太高，不過直接易於理解
問題：能不能在一個標準的國際象棋棋盤上放 8 個皇后，使她們相互之間不能互吃具體點就是，在一個 8*8 的棋盤上放皇后，皇后是所有方向上都可以移動的，現在要讓她們不能互吃的話就要使得她們不會在同一條線上
具體解法：從第一行第一列的位置開始放棋子（假定列優先），然後記錄其佔用的行斜直線的編號，然後放第二個棋子，在排除前面所有棋子的所佔的編號的情況下選擇到有效位置，然後繼續，直到放滿 8 個棋子為止
代碼如下：
/*
* 八皇后算法問題
*author CG
*2008 12 22
*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 8 /* 設置皇后數量為 8*/
int a [N], b [2*N + 1], c [2*N +1];/* 三個數組記錄各個方向上的皇后 */
int count = 0;/* 計數器 */
int Queen(int row) {
int col; /* 局部變量 */
for (col = 1 ; col < = N ; col++){
if (a[col - 1] + b[row + col - 2] + c[row - col + N - 1] == 0) {
/*
* 這裡這部很重要，用於判斷皇后位置是否符合條件，只有各個方向的直線上
* 都沒有皇后才符合條件
* a [col-1] 記錄第 col 列有無皇后，1 表示有。
* b [row+col-2] 記錄從左上數第 row+col-1 條斜率為 1 的線上有無皇后。
* c [row-col+N-1] 記錄從右上數第 row-col+N-1 條斜率為 -1 的線上有無皇后。
*/
a [col - 1] = 1; /* 更改數據 */
b[row + col - 2] = 1;
c[row - col + N - 1] = 1;
gotoxy(col \* 2 , row);/\* 畫皇后 \*/
putch('Q');
if (row < N){/\*如果沒有遍歷所有row\*/
Queen(row + 1); /\*繼續\*/
}
else {/\*遞歸結束\*/
count++; /\*計數器+1\*/
gotoxy(1 , N + 2);
printf("Solution No %d ", count);
getch();
}
a\[col - 1\] = 0; /\* 清空數據 \*/
b\[row + col - 2\] = 0;
c\[row - col + N-1\] = 0;
gotoxy(col \* 2 , row); /\* 清除圖像 \*/
putch('.');
}/\*if \*/
}/*for */
return 0;
}/*Queen */
int main()
{
int i, j;
clrscr ();/* 清屏 */
for (i = 1 ; i <= N ; i++){/* 畫棋盤 */
for(j = 1 ; j <= N ; j++){
gotoxy (i * 2 , j);/* 注意字符佔位問題大寫 Q 和點號佔兩個字符位 */
putch('.');
}/*for*/
}/*for*/
Queen (1); /* 開始回溯算法 */
gotoxy (1 , N + 3); /* 顯示最後結果 */
printf("%d Solution(s)n", count);
system("pause");
}/*main*/