《C編程技巧：117個問題解決方案示例 》 —3.8　解決八皇后問題

3.8　解決八皇后問題

問題

你想利用回溯法來解決八皇后問題。

解決方案

回溯法是一種通用算法，用于查找計算問題的一些或所有可能的解決方案。在回溯中，首先考慮所有可能的候選者（可能成功），然后丟棄無法成功的候選者。最后，只剩下那些成功解決問題的候選人。在國際象棋棋盤上，八個皇后的排列方式使得沒有皇后可以攻擊另一個皇后。一個成功的解決方案要求沒有兩個皇后在相同的行、列或對角線上。編寫一個C程序，依照以下規格說明使用遞歸來解決八皇后問題：

定義名為queen()的函數。兩個int值將作為輸入參數傳遞給此函數：棋盤上的行號和棋盤上的皇后數（在本例中為8）。

函數queen()以遞歸方式調用函數print()、函數place()以及函數queen()本身。

函數place()檢查將皇后放置在棋盤上方格的可能性。如果一切正常，則返回1，否則，它返回0。

函數print()在屏幕上顯示皇后的成功位置。

以下是使用這些規格說明編寫的C程序的代碼。在文本編輯器中鍵入以下C程序，并將其保存在文件夾C:\Code中，文件名為queens.c：

編譯并執行此程序。請注意，這個問題有92種成功的解決方案。執行開始時，屏幕上會顯示解決方案1，如此處所示。按Enter鍵，然后屏幕上顯示解決方案2。如果你對查看所有92種解決方案不感興趣，只需按住Enter鍵并保持幾秒鐘即可。

這個程序的運行結果在這里給出：

工作原理

LOC 5～10定義main()函數。在LOC 7中，int變量p的值設置為8，因為棋盤上的皇后數是8。在LOC 8中，調用函數queen()。queen()的第一個參數是int值1，它表示第1行，queen()的第二個參數是int變量p，p的值設置為int值8（即棋盤上的皇后個數）。LOC 47～61定義了函數queen()。函數queen()調用函數place()來檢查放置情況（正在考慮中）對于皇后是否安全。如果一切正常，則place()返回1，一旦找到了皇后的一種成功放置情況，那么函數queen()調用函數print()來在屏幕上顯示成功的放置情況，如LOC 56所示。在LOC 58中，函數queen()遞歸調用自己，進一步調查正在考慮的放置情況。

c語言 C 語言

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。