怎么使用C語言解決八皇后問題-創(chuàng)新互聯(lián)

這篇文章主要介紹了怎么使用C語言解決八皇后問題，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

成都創(chuàng)新互聯(lián)堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的滎陽網(wǎng)站設(shè)計(jì)、移動媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

前言

八皇后問題是一個(gè)古老而著名的問題。該問題是19世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在一個(gè)8*8國際象棋盤上，有8個(gè)皇后，每個(gè)皇后占一格；要求皇后之間不會出現(xiàn)相互“攻擊”的現(xiàn)象，即不能有兩個(gè)皇后處在同一行、同一列或同一對角線上。問共有多少種不同的方法？

回溯算法也叫試探法，它是一種搜索問題的解的方法。冋溯算法的基本思想是在一個(gè)包含所有解的解空間樹中，按照深度優(yōu)先的策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意結(jié)點(diǎn)時(shí)，總是先判斷該結(jié)點(diǎn)是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結(jié)點(diǎn)為根的子樹的系統(tǒng)搜索，逐層向其祖先結(jié)點(diǎn)回溯。否則，進(jìn)入該子樹，繼續(xù)按深度優(yōu)先的策略進(jìn)行搜索。回溯法在用來求問題的所有解時(shí)，要回溯到根，且根結(jié)點(diǎn)的所有子樹都已被搜索遍才結(jié)束。

八皇后問題有很多中解法，其中使用回溯法進(jìn)行求解是其中一種。而回溯發(fā)也是最直接的一種解法，也較容易理解。

八皇后問題的回溯法算法，可以采用一維數(shù)組來進(jìn)行處理。數(shù)組的下標(biāo)i表示棋盤上的第i列，a[i]的值表示皇后在第i列所放的位置。例如，a[1]=5，表示在棋盤的第例的第五行放一個(gè)皇后。程序中首先假定a[1]=1，表示第一個(gè)皇后放在棋盤的第一列的第一行的位置上，然后試探第二列中皇后可能的位置，找到合適的位置后，再處理后續(xù)的各列，這樣通過各列的反復(fù)試探，可以最終找出皇后的全部擺放方法。

八皇后問題可以使用回溯法進(jìn)行求解，程序?qū)崿F(xiàn)如下：

#include<stdio.h>

#define Queens 8 //定義結(jié)果數(shù)組的大小，也就是皇后的數(shù)目

int a[Queens+1];  //八皇后問題的皇后所在的行列位置，從1幵始算起，所以加1

int main(){

int i, k, flag, not_finish=1, count=0;

//正在處理的元素下標(biāo)，表示前i-1個(gè)元素已符合要求，正在處理第i個(gè)元素

i=1;

a[1]=1; //為數(shù)組的第一個(gè)元素賦初值

printf("八皇后的可能配置是:\n");

while(not_finish){ //not_finish=l:處理尚未結(jié)束

while(not_finish && i<=Queens){ //處理尚未結(jié)束且還沒處理到第Queens個(gè)元素

for(flag=1,k=1; flag && k<i; k++) //判斷是否有多個(gè)皇后在同一行

if(a[k]==a[i])

flag=0;

for (k=1; flag&&k<i; k++) //判斷是否有多個(gè)皇后在同一對角線

if( (a[i]==a[k]-(k-i)) || (a[i]==a[k]+(k-i)) )

flag=0;

if(!flag){ //若存在矛盾不滿足要求，需要重新設(shè)置第i個(gè)元素

if(a[i]==a[i-1]){ //若a[i]的值已經(jīng)經(jīng)過一圈追上a[i-1]的值

i--; //退回一步，重新試探處理前一個(gè)元素

if(i>1 && a[i]==Queens)

a[i]=1; //當(dāng)a[i]為Queens時(shí)將a[i]的值置1

else

if(i==1 && a[i]==Queens)

not_finish=0; //當(dāng)?shù)谝晃坏闹颠_(dá)到Queens時(shí)結(jié)束

else

a[i]++; //將a[il的值取下一個(gè)值

}else if(a[i] == Queens)

a[i]=1;

else

a[i]++; //將a[i]的值取下一個(gè)值

}else if(++i<=Queens)

if(a[i-1] == Queens )

a[i]=1; //若前一個(gè)元素的值為Queens則a[i]=l

else

a[i] = a[i-1]+1; //否則元素的值為前一個(gè)元素的下一個(gè)值

}

if(not_finish){

++count;

printf((count-1)%3 ? "\t[%2d]:" : "\n[%2d]:", count);

for(k=1; k<=Queens; k++) //輸出結(jié)果

printf(" %d", a[k]); 

if(a[Queens-1]<Queens )

a[Queens-1]++; //修改倒數(shù)第二位的值

else

a[Queens-1]=1;

i=Queens -1;  //開始尋找下一個(gè)滿足條件的解

}

}

}

輸出結(jié)果：

八皇后的可能配置是:

[ 1]: 1 5 8 6 3 7 2 4 [ 2]: 1 6 8 3 7 4 2 5 [ 3]: 1 7 4 6 8 2 5 3

[ 4]: 1 7 5 8 2 4 6 3 [ 5]: 2 4 6 8 3 1 7 5 [ 6]: 2 5 7 1 3 8 6 4

[ 7]: 2 5 7 4 1 8 6 3 [ 8]: 2 6 8 3 1 4 7 5 [ 9]: 2 6 1 7 4 8 3 5

[10]: 2 7 3 6 8 5 1 4 [11]: 2 7 5 8 1 4 6 3 [12]: 2 8 6 1 3 5 7 4

[13]: 3 5 7 1 4 2 8 6 [14]: 3 5 8 4 1 7 2 6 [15]: 3 5 2 8 1 7 4 6

[16]: 3 5 2 8 6 4 7 1 [17]: 3 6 8 1 4 7 5 2 [18]: 3 6 8 1 5 7 2 4

[19]: 3 6 8 2 4 1 7 5 [20]: 3 6 2 5 8 1 7 4 [21]: 3 6 2 7 1 4 8 5

[22]: 3 6 2 7 5 1 8 4 [23]: 3 6 4 1 8 5 7 2 [24]: 3 6 4 2 8 5 7 1

[25]: 3 7 2 8 5 1 4 6 [26]: 3 7 2 8 6 4 1 5 [27]: 3 8 4 7 1 6 2 5

[28]: 3 1 7 5 8 2 4 6 [29]: 4 6 8 2 7 1 3 5 [30]: 4 6 8 3 1 7 5 2

[31]: 4 6 1 5 2 8 3 7 [32]: 4 7 1 8 5 2 6 3 [33]: 4 7 3 8 2 5 1 6

[34]: 4 7 5 2 6 1 3 8 [35]: 4 7 5 3 1 6 8 2 [36]: 4 8 1 3 6 2 7 5

[37]: 4 8 1 5 7 2 6 3 [38]: 4 8 5 3 1 7 2 6 [39]: 4 1 5 8 2 7 3 6

[40]: 4 1 5 8 6 3 7 2 [41]: 4 2 5 8 6 1 3 7 [42]: 4 2 7 3 6 8 1 5

[43]: 4 2 7 3 6 8 5 1 [44]: 4 2 7 5 1 8 6 3 [45]: 4 2 8 5 7 1 3 6

[46]: 4 2 8 6 1 3 5 7 [47]: 5 7 1 3 8 6 4 2 [48]: 5 7 1 4 2 8 6 3

[49]: 5 7 2 4 8 1 3 6 [50]: 5 7 2 6 3 1 4 8 [51]: 5 7 2 6 3 1 8 4

[52]: 5 7 4 1 3 8 6 2 [53]: 5 8 4 1 3 6 2 7 [54]: 5 8 4 1 7 2 6 3

[55]: 5 1 4 6 8 2 7 3 [56]: 5 1 8 4 2 7 3 6 [57]: 5 1 8 6 3 7 2 4

[58]: 5 2 4 6 8 3 1 7 [59]: 5 2 4 7 3 8 6 1 [60]: 5 2 6 1 7 4 8 3

[61]: 5 2 8 1 4 7 3 6 [62]: 5 3 8 4 7 1 6 2 [63]: 5 3 1 6 8 2 4 7

[64]: 5 3 1 7 2 8 6 4 [65]: 6 8 2 4 1 7 5 3 [66]: 6 1 5 2 8 3 7 4

[67]: 6 2 7 1 3 5 8 4 [68]: 6 2 7 1 4 8 5 3 [69]: 6 3 5 7 1 4 2 8

[70]: 6 3 5 8 1 4 2 7 [71]: 6 3 7 2 4 8 1 5 [72]: 6 3 7 2 8 5 1 4

[73]: 6 3 7 4 1 8 2 5 [74]: 6 3 1 7 5 8 2 4 [75]: 6 3 1 8 4 2 7 5

[76]: 6 3 1 8 5 2 4 7 [77]: 6 4 7 1 3 5 2 8 [78]: 6 4 7 1 8 2 5 3

[79]: 6 4 1 5 8 2 7 3 [80]: 6 4 2 8 5 7 1 3 [81]: 7 1 3 8 6 4 2 5

[82]: 7 2 4 1 8 5 3 6 [83]: 7 2 6 3 1 4 8 5 [84]: 7 3 8 2 5 1 6 4

[85]: 7 3 1 6 8 5 2 4 [86]: 7 4 2 5 8 1 3 6 [87]: 7 4 2 8 6 1 3 5

[88]: 7 5 3 1 6 8 2 4 [89]: 8 2 4 1 7 5 3 6 [90]: 8 2 5 3 1 7 4 6

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“怎么使用C語言解決八皇后問題”這篇文章對大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)建站，關(guān)注創(chuàng)新互聯(lián)網(wǎng)站建設(shè)公司行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站muchs.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文題目：怎么使用C語言解決八皇后問題-創(chuàng)新互聯(lián)
本文地址：http://muchs.cn/article22/cspdcc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、微信公眾號、Google、外貿(mào)建站、網(wǎng)站維護(hù)、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)