回溯算法解決八皇后問題(包含C語言實現代碼)

八皇后問題是以西洋棋為背景的問題：有八個皇后（可以當成八個棋子），如何在 8*8 的棋盤中放置八個皇后，使得任意兩個皇后都不在同一條橫線、縱線或者斜線上。

圖 2 八皇后問題示例（#代表皇后）

八皇后問題是使用回溯算法解決的典型案例。算法的解決思路是：

從棋盤的第一行開始，從第一個位置開始，依次判斷當前位置是否能夠放置皇后，判斷的依據為：同該行之前的所有行中皇后的所在位置進行比較，如果在同一列，或者在同一條斜線上（斜線有兩條，為正方形的兩個對角線），都不符合要求，繼續檢驗後序的位置。

如果該行所有位置都不符合要求，則回溯到前一行，改變皇后的位置，繼續試探。

如果試探到最後一行，所有皇后擺放完畢，則直接列印出 8*8 的棋盤。最後一定要記得將棋盤恢復原樣，避免影響下一次擺放。

實現代碼：

#include <stdio.h>int Queenes[8]={0},Counts=0;int Check(int line,int list){        for (int index=0; index<line; index++) {                int data=Queenes[index];                if (list==data) {            return 0;        }                if ((index+data)==(line+list)) {            return 0;        }                if ((index-data)==(line-list)) {            return 0;        }    }        return 1;}void print(){    for (int line = 0; line < 8; line++)    {        int list;        for (list = 0; list < Queenes[line]; list++)            printf("0");        printf("#");        for (list = Queenes[line] + 1; list < 8; list++){            printf("0");        }        printf("\n");    }    printf("================\n");}void eight_queen(int line){        for (int list=0; list<8; list++) {                if (Check(line, list)) {                        Queenes[line]=list;                        if (line==7) {                                Counts++;                                print();                                Queenes[line]=0;                return;            }                        eight_queen(line+1);                        Queenes[line]=0;        }    }}int main() {        eight_queen(0);    printf("擺放的方式有%d種",Counts);    return 0;}
大家可以自己運行一下程序，查看運行結果，由於八皇后問題有 92 種擺法，這裡不一一列舉。