本文共 3132 字，大约阅读时间需要 10 分钟。

什么是八皇后问题？

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

图示

像这样的。

解法之一

#include
   
    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，应该仅把有落子的地方置一即可，不然会对回溯造成不可估量的麻烦。

转载地址：https://lion-wu.blog.csdn.net/article/details/107639403 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！