本文實例講述了C語言基于回溯算法解決八皇后問題的方法。分享給大家供大家參考，具體如下：
問題描述：
八皇后問題，是一個古老而著名的問題，是回溯算法的典型案例：在8X8格的國際象棋棋盤上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
問題求解：
采用回溯算法，即從第一行開始，依次探查可以放置皇后的位置，若找到，則放置皇后，開始探查下一行；若該行沒有位置可以放置皇后，則回溯至上一行，清除該行放置皇后的信息，從該行原本放置皇后的下一個位置開始探查可以放置皇后的位置。求所有解時，每找到一組解，就清除這一組解最后一個皇后的位置信息，開始探查該行另外一個可以放置皇后的位置，依次回溯求解。
存儲結構：
一維數組：col[8]：存放第i列有無皇后的標記信息
一維數組：left[15]：存放每一條左斜線上的有無皇后的標記信息
一維數組：right[15]：存放每一條右直線上有無皇后的標記信息
一維數組：Q[8]：存放第i行的皇后的列下標
代碼實現：
#include<stdio.h>#define N 8int col[N] = { 0 };int right[2 * N - 1] = { 0 };int left[2 * N - 1] = { 0 };int Q[N];int cnt = 0;void Print(){ int i; for (i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (Q[i] == j) printf("■"); else printf("□"); } printf("/n"); } printf("==========================/n"); cnt++;}void Queen(int i){ int j; for (j = 0; j < N; j++) { if ((!col[j]) && (!left[i + j]) && (!right[7 + i - j])) { Q[i] = j;//放皇后 col[j] = 1; left[i + j] = 1; right[N - 1 + i - j] = 1;//已有皇后的標記 if (i < N - 1) { Queen(i + 1); } else { Print(); } col[j] = 0; right[N - 1 + i - j] = 0; left[i + j] = 0;//清除標記，查找下一組解 } }}int main(void){ Queen(0); printf("%d", cnt); getchar(); return 0;}運行結果：
一共92組解，前面結果略去。。
希望本文所述對大家C語言程序設計有所幫助。
新聞熱點
疑難解答
