四皇后问题求解

　　本章内容来自《妙趣横生的算法》一书中。
　　回溯法是一种非常有效，适用范围相当广泛的算法设计思想。许多复杂的问题，规模较大的问题都可以使用回溯法求解。因此回溯法又有＂通用解题方法＂的美称。
　　回溯法的基本思想是：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含＂剪枝＂操作。
　　如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样根结点的所有子树都被探索到才结束。如果只要求解问题的一个解，问题的最终解，因此要跳过对以该结点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程叫做解空间树的那么在探索解空间树时，只要搜索到问题的一个解就可以结束了。
　　应用回溯法的思想求解四皇后问题
　　分析：
　　上面一节中已经详细介绍了回溯法解决四皇后问题的基本过程。在这里将给出具体的算法描述和程序清单。
　　其实在解决四皇后问题时，并不一定要真的构建出这样一棵解空间树，它完全可以通过一个递归回溯来模拟。所谓解空间树只是一个逻辑上的抽象。当然也可以用树结构来真实地创建出一棵解空间树，不过那样会比较浪费空间资源。 #include ＂stdio.h＂ int count=0;							/*记录四皇后问题解的个数*/ int isCorrect(int i,int j,int (*Q)[4]) {    int s,t;    for(s=i,t=0;t<4;t++)    if(Q[s][t]==1 && t!=j)return 0;		/*判断行*/     for(t=j,s=0;s<4;s++)    if(Q[s][t]==1 && s!=i)return 0;		/*判断列*/     for(s=i-1,t=j-1;s>=0&&t>=0;s--,t--)    if(Q[s][t] == 1)return 0;			/*判断左上方*/     for(s=i+1,t=j+1;s<4&&t<4;s++,t++)    if(Q[s][t] == 1) return 0;			/*判断右下方*/     for(s=i-1,t=j+1;s>=0&&t<4;s--,t++)    if(Q[s][t] == 1) return 0;			/*判断右上方*/     for(s=i+1,t=j-1;s<4&&t>=0;s++,t--)    if(Q[s][t] == 1) return 0;			/*判断左下方*/     return 1;								/*否则返回1*/ }  void Queen(int j,int (*Q)[4]){    int i , k;    if(j==4)    {										/*得到了一个解*/         for(i=0;i<4;i++)         {             for(k=0;k<4;k++)                 printf(＂%d ＂,Q[i][k]);             printf(＂ ＂);         } 		 printf(＂ ＂);         getche(); 		count++; 		return;             }    for(i=0;i<4;i++)    { 	   if(isCorrect(i,j,Q))				/*如果Q[i][j]可以放置皇后*/         { 		             Q[i][j] = 1;            		/*放置皇后*/             Queen(j+1,Q) ;				/*深度优先搜索解空间树*/ 			Q[i][j] = 0;         }    } }  main() {     int Q[4][4]; 	int i,j; 	for( i=0;i<4;i++)        for( j=0;j<4;j++)             Q[i][j] = 0;					/*初始化数组Q*/     Queen(0,Q);							/*执行四皇后求解*/ 	printf(＂The number of the answers of FOUR_QUEEN are %d＂,count);     getche(); }
　　运行结果：