任務(wù)描述

本關(guān)任務(wù)：國際象棋中的皇后可以沿著水平線，垂直線，或者斜線前進，吃掉遇到的所有棋子，如果棋盤上有八個皇后，則這八個皇后如何相安無事的放置在棋盤上，1970年與1971年， E.W.Dijkstra與N.Wirth曾經(jīng)用這個問題來講解程式設(shè)計之技巧。該題要求N皇后的放置結(jié)果共有多少種。

相關(guān)知識

回溯法

測試說明

平臺會對你編寫的代碼進行測試：
輸入描述：輸入一個正整數(shù)N（N小于16）
輸出描述：輸出結(jié)果

例 測試輸入：8
預(yù)期輸出：92

解析：

放置皇后時，對所有列進行遍歷，并且一一判斷能不能進行放置。可以放置便進行遞歸，一種方法成功后回溯尋找下一種。

//下面編寫代碼 #include <stdio.h> #include <stdlib.h> #define N 16 int q[N]; // 下標(biāo)為皇后的行號，值為列號 int count = 0; // 統(tǒng)計解得個數(shù)// 檢驗第i行的k列上是否可以擺放皇后 int find(int i,int k) {int j=1;while(j<i) // 通過前面已放置皇后的行來判斷這一列是否可以放置{// 第j行的皇后是否在k列或(j,q[j])與(i,k)是否在斜線上if(q[j]==k ||abs(j-i)==abs(q[j]-k))return 0; // 不能放置j++;}return 1; // 可以放置 } // 放置皇后到棋盤上 void place(int k,int n) {int j;if(k>n) // 終止條件count++; // 終止代表一種放法實現(xiàn)，計數(shù)加一else{for(j=1;j<=n;j++) // 試探第k行的每一個列{if(find(k,j)){q[k] = j; // 存入皇后存放的行列屬性place(k+1,n); // 遞歸}}} }int main(void) {int n;scanf("%d",&n); place(1,n);printf("%d", count);return 0; }

總結(jié)

以上是生活随笔為你收集整理的N皇后（C语言）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。