四皇后问题求解

本章内容来自《妙趣横生的算法》一书中。

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

回溯法的基本思想是:在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去;如果该结点不包含问题的解,那就说明以该结点为根结点的子树一定不包含“剪枝”操作。

如果应用回溯法求解问题的所有解,要回溯到解空间树的树根,这样根结点的所有子树都被探索到才结束。如果只要求解问题的一个解,问题的最终解,因此要跳过对以该结点为根的子树的系统探索,逐层向其祖先结点回溯。这个过程叫做解空间树的那么在探索解空间树时,只要搜索到问题的一个解就可以结束了。

应用回溯法的思想求解四皇后问题

分析:

上面一节中已经详细介绍了回溯法解决四皇后问题的基本过程。在这里将给出具体的算法描述和程序清单。

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

#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();
}

运行结果:

四皇后问题求解

展开阅读全文

页面更新:2024-03-03

标签:子树   递归   皇后   结点   妙趣横生   算法   深度   过程   思想   空间

1 2 3 4 5

上滑加载更多 ↓
推荐阅读:
友情链接:
更多:

本站资料均由网友自行发布提供,仅用于学习交流。如有版权问题,请与我联系,QQ:4156828  

© CopyRight 2008-2024 All Rights Reserved. Powered By bs178.com 闽ICP备11008920号-3
闽公网安备35020302034844号

Top