专栏首页CSDN搜“看,未来”【C++】八皇后问题(竖列递进)

【C++】八皇后问题(竖列递进)

什么是八皇后问题?

八皇后问题是一个古老的问题,于1848年由一位国际象棋棋手提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,如何求解?

图示

像这样的。

解法之一

#include<iostream>

using namespace std;

#define MAX_NUM 8		//皇后数量

int queen[MAX_NUM][MAX_NUM] = { 0 };

bool check(int x, int y) {	//检查一个坐标是否可以放置
	for (int i = 0; i < y; i++) {
		if (queen[x][i] == 1) {	//这一行是否可以存在
			return false;
		}
		if (x - 1 - i > 0 && queen[x - 1 - i][y - 1 - i] == 1) {	//检查左斜列
			return false;
		}
		if (x + 1 + i < MAX_NUM && queen[x + 1 + i][y + 1 + i] == 1) {	//检查右斜列
			return false;
		}
	}
	queen[x][y] = 1;
	return true;
}

void showQueen() {
	for (int i = 0; i < MAX_NUM; i++) {
		for (int j = 0; j < MAX_NUM; j++) {
			cout << queen[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}

bool settleQueen(int x) {
	if (x == MAX_NUM) {	//遍历完毕,找到答案
		return true;
	}
	for (int i = 0; i < MAX_NUM; i++) {
		for (int y = 0; y < MAX_NUM; y++) {
			queen[y][x] = 0;	//清空当前列,省的回溯的时候被打扰
		}
		if (check(i,x)) {	//如果这行找着了
			queen[i][x] = 1;
			showQueen();	//直观测试结果
			if (settleQueen(x + 1)) {	//是时候往左了
				return true;	//一路往左
			}
		}
	}
	return false;	//如果不行,就退回来
}

测试结果

测试过程打印:

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0


main中的打印

1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0

C:\Users\asus\source\repos\EightQuene\Debug\EightQuene.exe (进程 9184)已退出,代码为 0。 按任意键关闭此窗口. . .

其他解法

之前也见过其他解法的讲解,有横着来的,还有用位图来解决的。 不过不要被上面那几张图给迷惑了,一定不要把不能走的位置置1,应该仅把有落子的地方置一即可,不然会对回溯造成不可估量的麻烦。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员必备数据结构:栈

    栈有很多用途,也分很多种类,顺序栈、双端栈、单调栈、链栈等。让哥哥带你,深入浅出堆栈系列。坐好上车咯。

    看、未来
  • sqlite3数据库封装 - 动态链接库

    将资源文件放在当前项目工程文件下,编译指令:g++ *.cpp -o name -L./ -lmydb //名字自己起 ②第三方库形式

    看、未来
  • 【C++】八大排序算法 :GIF + 亲测代码 +专项练习平台

    相邻两个数两两相比,n[i]跟n[j+1]比,如果n[i]>n[j+1],则将两个数进行交换

    看、未来
  • 破解文字加密第三弹之深扒天眼查

    凡是加密的地方,它的标签属性都是:class='tyc-num lh24',已经在下图用红色框框出,现在看它的字体,用青色框框出,它的字体是"tyc-num" ...

    前端皮皮
  • Leetcode Golang 110. Balanced Binary Tree.go

    版权声明:原创勿转 https://blog.csdn.net/anakinsun/article/details/88965643

    anakinsun
  • 你不知道的gRPC反向代理

    可用性、可靠性和扩展性是衡量后台服务的基本标准,HTTP反向代理,是任何一个提供大型Web服务后台所必备的,用以提高服务的这些基础参数,且通过支持到负载均衡而进...

    netkiddy
  • Android实现ViewPager无限循环效果(一)

    本文实例为大家分享了Android实现ViewPager无限循环的具体代码,供大家参考,具体内容如下

    砸漏
  • 手写一个解析器

    ? 作者:jolamjiang,腾讯 WXG 前端开发工程师 前言 最近工作中有一些同学在做一些效能工具的时候遇到需要写一门领域相关语言(DSL)及其解析器的...

    腾讯技术工程官方号
  • SELinux的基本使用

    从进入了 CentOS 5.x 之后的 CentOS 版本中 (当然包括 CentOS 7),SELinux 已经是个非常完备的核心模块了!尤其 CentOS ...

    小柒吃地瓜
  • 巧用 CSS 实现酷炫的充电动画

    欧了,勉强就是它了。有了电池,那接下来直接充电吧。最最简单的动画,那应该是用色彩把整个电池灌满即可。

    Sb_Coco

扫码关注云+社区

领取腾讯云代金券