程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> 八皇後問題與回溯算法

八皇後問題與回溯算法

編輯:關於C

八皇後問題是在8*8的棋盤上放置8枚皇後,使得棋盤中每個縱向、橫向、左上至右下斜向、右上至左下斜向均只有一枚皇後。八皇後的一個可行解如圖所示:

             

\

   

\

         

\

                       

\

     

\

                   

\

                 

\

       

\

       

思路

對於八皇後的求解可采用回溯算法,從上至下依次在每一行放置皇後,進行搜索,若在某一行的任意一列放置皇後均不能滿足要求,則不再向下搜索,而進行回溯,回溯至有其他列可放置皇後的一行,再向下搜索,直到搜索至最後一行,找到可行解,輸出。

可以使用遞歸函數實現上述回溯算法,遞歸函數用於求解在某一行放置皇後,具體代碼如下所示

代碼
1.    #include <stdlib.h>
2.    #include <stdio.h>
3.   
4.    int m[8][8] = {0};//表示棋盤,初始為0,表示未放置皇後
5.    int num = 0;//解數目
6.   
7.    //對於棋盤前row-1行已放置好皇後
8.    //檢查在第row行、第column列放置一枚皇後是否可行
9.    bool check(int row,int column)
10.   {
11.       if(row==1) return true;
12.       int i,j;
13.       //縱向只能有一枚皇後
14.       for(i=0;i<=row-2;i++)
15.       {
16.           if(m[i][column-1]==1) return false;
17.       }
18.       //左上至右下只能有一枚皇後
19.       i = row-2;
20.       j = i-(row-column);
21.       while(i>=0&&j>=0)
22.       {
23.           if(m[i][j]==1) return false;
24.           i--;
25.           j--;
26.       }
27.       //右上至左下只能有一枚皇後
28.       i = row-2;
29.       j = row+column-i-2;
30.       while(i>=0&&j<=7)
31.       {
32.           if(m[i][j]==1) return false;
33.           i--;
34.           j++;
35.       }
36.       return true;
37.   }
38.  
39.   //當已放置8枚皇後,為可行解時,輸出棋盤
40.   void output()
41.   {
42.       int i,j;
43.       num++;
44.       printf("answer %d:\n",num);
45.       for(i=0;i<8;i++)
46.       {
47.           for(j=0;j<8;j++) printf("%d ",m[i][j]);
48.           printf("\n");
49.       }
50.   }
51.  
52.   //采用遞歸函數實現八皇後回溯算法
53.   //該函數求解當棋盤前row-1行已放置好皇後,在第row行放置皇後
54.   void solve(int row)
55.   {
56.       int j;
57.       //考慮在第row行的各列放置皇後
58.       for (j=0;j<8;j++)
59.       {
60.           //在其中一列放置皇後
61.           m[row-1][j] = 1;
62.           //檢查在該列放置皇後是否可行
63.           if (check(row,j+1)==true)
64.           {
65.               //若該列可放置皇後,且該列為最後一列,則找到一可行解,輸出
66.               if(row==8) output();
67.               //若該列可放置皇後,則向下一行,繼續搜索、求解
68.               else solve(row+1);
69.           }
70.           //取出該列的皇後,進行回溯,在其他列放置皇後
71.           m[row-1][j] = 0;
72.       }
73.   }
74.  
75.   //主函數
76.   int main()
77.   {
78.       //求解八皇後問題
79.       solve(1);
80.       return 0;
81.   }
 



 

\

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved