八皇后问题并输出棋盘(回溯法)

2024-04-28 03:08

本文主要是介绍八皇后问题并输出棋盘(回溯法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

八皇后问题并输出棋盘

题目:

在8×8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
并将答案按照国际象棋棋盘样式输出

解题思路:

1.求解决方案
输入:皇后的个数 n
输出:n 皇后的解的棋盘
初始化解向量 x[n]=-1
解:

1K=1
2、While(k>=1)3、把皇后摆放在下一列的位置,x[k]++4、从 x[k]开始依次考察下一列,如果皇后 k 摆放在 x[k]位置不发生冲突,转 5,否则 x[k]++试探下一列5、若 n 个皇后都已全部摆放,则输出一个解,算法结束;6、若尚有皇后没摆放,k++,转步骤 5 转下一个皇后7、若 x[k]出界,回溯,x[k]=-1,k--,转步骤 3 重新摆放皇后 k8、退出循环,说明 n 皇后问题无解

2.输出棋盘
从国际象棋棋盘可以看出,黑格和白格交替分布,相邻两行分布错位,所以按照这个规律,写出如下函数:

void printChess(int *a) {for (int i = 0; i < N; ++i) { //遍历每一行for (int j = 0; j < N; ++j) { //遍历每一列if (i%2==0 && j%2==0)cout << (a[i] == j ? "K" : "+");else if (i%2==1 && j%2==0)cout << (a[i]== j ? "`" : ">");else if (i%2==0 && j%2==1)cout << (a[i] == j ? "`" : ">");else if (i%2==1 && j%2==1)cout << (a[i] == j ? "K" : "+");} //如果标记数组中这一行的皇后放在j位置,则输出X,否则输出-,cout << endl; //每一行输出一个换行}cout << endl;
}

这里用的字体是Chess Adventure,用户需要自行下载并安装到自己的电脑中,链接如下:http://www.fontsaddict.com/font/chess-adventurer.html
如果无法下载请私信我。

其中‘K’,‘+’,‘`’,‘>’代表着白底皇后,白格,黑底皇后,黑格,当然也可以选择其他符号

源代码

#include<iostream>
#include <math.h>  
using namespace std;          
const int N = 8;                       
int x[N] = {-1};               //将数组x[N]初始化为-1int Place(int k)                    //考察皇后k放置在x[k]列是否发生冲突
{for (int i = 0; i < k; i++)   if (x[i] == x[k] || abs(i - k) == abs( x[i] - x[k]))  //冲突,返回1return 1;                                          return 0;                                            //不冲突,返回0
}void printChess(int *a) {for (int i = 0; i < N; ++i) { //遍历每一行for (int j = 0; j < N; ++j) { //遍历每一列if (i%2==0 && j%2==0)cout << (a[i] == j ? "K" : "+");else if (i%2==1 && j%2==0)cout << (a[i]== j ? "`" : ">");else if (i%2==0 && j%2==1)cout << (a[i] == j ? "`" : ">");else if (i%2==1 && j%2==1)cout << (a[i] == j ? "K" : "+");} //如果标记数组中这一行的皇后放在j位置,则输出X,否则输出-,cout << endl; //每一行输出一个换行}cout << endl;
}void Queue(int n)                      
{int k = 0;  int solution=0;                         while (k >= 0)                               //摆放皇后{x[k]++;                                       //在下一列摆放皇后kwhile (x[k] < n && Place(k) == 1)                           //发生冲突x[k]++;                                       //皇后k试探下一列if (x[k] < n && k == n - 1 )                         //得到一个解,输出{cout<<"Solutions:"<<solution+1<<endl;printChess(x);solution++;x[k--] = -1;                  //重置x[k],回溯,重新摆放皇后k}else if (x[k] < n && k < n - 1)                         //尚有皇后未摆放k = k + 1;                               //准备摆放下一个皇后elsex[k--] = -1;                  //重置x[k],回溯,重新摆放皇后k}cout<<"Solutions="<<solution<<endl;cout<<"end"<<endl;
}int main( )
{Queue(8);         return 0;                      
}

结果

1.输出的文本(部分):
在这里插入图片描述
2.将其复制到Word中修改字体(部分)
在这里插入图片描述

这篇关于八皇后问题并输出棋盘(回溯法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/942186

相关文章

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Spring MVC跨域问题及解决

《SpringMVC跨域问题及解决》:本文主要介绍SpringMVC跨域问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录跨域问题不同的域同源策略解决方法1.CORS2.jsONP3.局部解决方案4.全局解决方法总结跨域问题不同的域协议、域名、端口

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

Spring AI集成DeepSeek实现流式输出的操作方法

《SpringAI集成DeepSeek实现流式输出的操作方法》本文介绍了如何在SpringBoot中使用Sse(Server-SentEvents)技术实现流式输出,后端使用SpringMVC中的S... 目录一、后端代码二、前端代码三、运行项目小天有话说题外话参考资料前面一篇文章我们实现了《Spring

基于.NET编写工具类解决JSON乱码问题

《基于.NET编写工具类解决JSON乱码问题》在开发过程中,我们经常会遇到JSON数据处理的问题,尤其是在数据传输和解析过程中,很容易出现编码错误导致的乱码问题,下面我们就来编写一个.NET工具类来解... 目录问题背景核心原理工具类实现使用示例总结在开发过程中,我们经常会遇到jsON数据处理的问题,尤其是

springboot3.4和mybatis plus的版本问题的解决

《springboot3.4和mybatisplus的版本问题的解决》本文主要介绍了springboot3.4和mybatisplus的版本问题的解决,主要由于SpringBoot3.4与MyBat... 报错1:spring-boot-starter/3.4.0/spring-boot-starter-

在 Spring Boot 中使用异步线程时的 HttpServletRequest 复用问题记录

《在SpringBoot中使用异步线程时的HttpServletRequest复用问题记录》文章讨论了在SpringBoot中使用异步线程时,由于HttpServletRequest复用导致... 目录一、问题描述:异步线程操作导致请求复用时 Cookie 解析失败1. 场景背景2. 问题根源二、问题详细分