• N 皇后问题(回溯法)


    N 皇后问题(回溯法)

    题目描述:

    国际象棋中,皇后是最厉害的棋子,可以横走、直走,还可以斜走。棋手马克斯·贝瑟尔 1848 年提出著名的八皇后问题:即在 8 × 8 的棋盘上摆放八个皇后,使其不能互相攻击 —— 即任意两个皇后都不能处于同一行、同一列或同一条斜线上。

    现在我们把棋盘扩展到 n×n 的棋盘上摆放 n 个皇后,请问该怎么摆?

    请编写程序,输入正整数 n,输出全部摆法(棋盘格子空白处显示句点“.”,皇后处显示字母“Q”,每两个字符之间空一格)。

    输入格式

    正整数 n(n>0)

    输出格式

    若问题有解,则输出全部摆法(每两种摆法之间空一行)。
    若问题无解,则输出 None。

    要求:试探的顺序按从上到下逐行进行,其中每一行按从左到右的逐格进行,请参看输出样例2。

    输入样例1
    3
    
    • 1
    输出样例1
    None
    
    • 1
    输入样例2
    6
    
    • 1
    输出样例2
    . Q . . . .
    . . . Q . .
    . . . . . Q
    Q . . . . .
    . . Q . . .
    . . . . Q .
    
    . . Q . . .
    . . . . . Q
    . Q . . . .
    . . . . Q .
    Q . . . . .
    . . . Q . .
    
    . . . Q . .
    Q . . . . .
    . . . . Q .
    . Q . . . .
    . . . . . Q
    . . Q . . .
    
    . . . . Q .
    . . Q . . .
    Q . . . . .
    . . . . . Q
    . . . Q . .
    . Q . . . .
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    思路:

    标记上对角线和下对角线时。上对角线的每一个点可以用行减列表示,这样使得每一条上对角线上的点都是一样的数,方便标记,上部分的行减列为负数,下部分为正数所以加7使上对角线用数组方便标记。 下对角线行加列这样使得每一条下对角线上的点都是一样的数,方便标记,两部分都为正数无需加7。

    代码:

    #include
    #include
    int queen[9];  //用于存放每一行皇后放置的列数 
    int row[9];    //用于标志一列是否放置了皇后 
    int A[16];     //用于标志上对角线是否放置了皇后 
    int B[16];     //用于标志下对角线是否放置了皇后 
    int count,n;   //用于输出时每一种可能的序号 
    
    void print();            //输出每一种放置可能的函数 
    void backtrack(int m);   //放置皇后的函数 
    
    int main()
    {
    	scanf("%d",&n);   //输入要放置几个皇后 
    	backtrack(1);     //从第1行开始放置皇后 
    	return 0;
    }
    
    void backtrack(int m) 
    {     //在第m行放置皇后 
    	for(int i=1;i<=n;i++) //遍历的是列 
    	{   //从一行中的每一个点开始遍历,直至找到合适点 
    		if(row[i]==0&&A[m-i+n]==0&&B[m+i]==0)
    		{   //判断m行i列的列、上对角线和下对角线是否有皇后 
    			queen[m]=i;    //满足条件就放置
    			row[i]=1;      //该列标志为有皇后 
    			A[m-i+n]=1;  //上对角线标志为有皇后 
    			B[m+i]=1;      //下对角线标志为有皇后
    			if(m<n)      //如果皇后没放置完,递归开始放置下一行 
    				backtrack(m+1);
    			else   //如果放置完了就打印这一种可能 
    				print();  
    			row[i]=0;
    			A[m-i+n]=0;  //取消放置,回溯其他可能
    			B[m+i]=0; 
    		}
    	}
    }
    void print()
    {
    	int tatle[9][9];  //用于打印棋盘的数组 
    	for(int i=1;i<=n;i++) 
    		for(int k=1;k<=n;k++) 
    			tatle[i][k]='.'; 
    	count++;
    	printf("NO:%d\n",count);
    	for(int i=1;i<=n;i++)  //queen中存放的是每行皇后放置的列 
    		tatle[i][queen[i]]='Q'; //将每行放置的皇后标志出来 
    	for(int i=1;i<=n;i++)
    	{    //输出棋盘 
    		for(int k=1;k<=n;k++)  
    			printf("%c ",tatle[i][k]);	
    		printf("\n");	
    	}	
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
  • 相关阅读:
    NoSQL入门-NoSQL虚拟机安装注意事项
    2023华为杯研究生数学建模D题思路代码分析
    Spring Boot实现热部署有哪几种方式
    Flir Blackfly S 工业相机:自动曝光配置及代码
    QT 通用算法可以在任何提供STL风格迭代器的容器类上使用
    从零搭建react + webpack项目
    docker swarm集群部署rabbit-mq
    Linux源码&文件系统目录结构
    Xuperchain竞赛环境安装与工作环境搭建
    家谱文化研究②:比赘婿更不光彩的家庭角色?何雨柱还乐在其中
  • 原文地址:https://blog.csdn.net/zhouhaoNB_/article/details/126775548