回溯法基本思想是什么（回溯法的应用）

回溯法是一种非常有效，适用范围相当广泛的算法设计思想。许多复杂的问题，规模较大的问题都可以使用回溯法求解。因此回溯法又有“通用解题方法”的美称。本章将详细介绍回溯法的算法思想。

回溯法的基本思想是：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去；如果该结点不包含问题的解，那就说明以该结点为根结点的子树一定不包含问题的最终解，因此要跳过对以该结点为根的子树的系统探索，逐层向其祖先结点回溯。这个过程叫做解空间树的“剪枝”操作。

如果应用回溯法求解问题的所有解，要回溯到解空间树的树根，这样根结点的所有子树都被探索到才结束。如果只要求解问题的一个解，那么在探索解空间树时，只要搜索到问题的一个解就可以结束了。

四皇后问题求解

其实在解决四皇后问题时，并不一定要真的构建出这样一棵解空间树，它完全可以通过一个递归回溯来模拟。所谓解空间树只是一个逻辑上的抽象。当然也可以用树结构来真实地创建出一棵解空间树，不过那样会比较浪费空间资源。

源代码：

#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("\n");
        }
		 printf("\n");
        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();
}

运行结果：