八皇后回溯法结题思路（C++）

科普：

    八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。

最近又重新拾起C++++

今天心血来潮做了一个比较经典的算法问题

其实思路很简单，做起来也没有多难

下面开始先贴出源代码

// baqueen.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <math.h>
/***********************************
*地图形式来打印皇后的位置
************************************/
void showQueens(int queenArr[], int nLen,int nSoLution)
{
printf("===========皇后解法第%d=============n",nSoLution);
for (int i = 0; i < nLen; i++)
{
//打印皇后前面的部分
if (queenArr[i] == -1)
{
for (int j = 0; j < nLen; j++)
{
printf("○");
}
printf("n");
continue;
}
//打印皇后前面的空余部分。。。
for (int j = 0; j < queenArr[i]; j++)
{
printf("○");
}
printf("●");//打印皇后
for (int j= 0; j< nLen - queenArr[i] - 1; j++)
{
//打印皇后后面的空余部分
printf("○");
}
printf("n");
}
printf("===============================n");
}
bool isClash(int queenArr[])
{
for (int i = 1; i <= 10; i++)
{
for (int  j = 0;  j <= i-1;  j++)
{
if (queenArr[i] == queenArr[j])
{
//如果两个相等，两个则在同一列
return true;
}
if (abs(queenArr[i] - queenArr[j]) == abs(i-j))
{
return true;
}
}
}
return false;
}
void enumQueention(int queenArr[],int &nSolution)
{
for (queenArr[0] = 0; queenArr[0] < 10 ; queenArr[0]++)
for ( queenArr[1] = 0; queenArr[1] < 10; queenArr[1]++)
for (queenArr[2] = 0; queenArr[2] < 10; queenArr[2]++)
for (queenArr[3] = 0; queenArr[3] < 10; queenArr[3]++)
for (queenArr[4] = 0; queenArr[4] < 10; queenArr[4]++)
for (queenArr[5] = 0; queenArr[5] < 10; queenArr[5]++)
for (queenArr[6] = 0; queenArr[6] < 10; queenArr[6]++)
for (queenArr[7] = 0; queenArr[7] < 10; queenArr[7]++)
for ( queenArr[8] = 0; queenArr[8] < 10; queenArr[8]++)
for ( queenArr[9] = 0; queenArr[9] < 10; queenArr[9]++)
{
//判断当前方案是否有效
if (isClash(queenArr))
{
continue;
}
else
{
nSolution++;
//当前方案ok，打印方案出来
showQueens(queenArr, 10, nSolution);
}
}
}
int main()
{
/*
定义一个数组代表一个皇后的位置
通过下标来代表皇后的位置
*/
int queenArr[10];
int nSoLution = 0;//解法数量
enumQueention(queenArr,nSoLution);
    return 0;
}

上面的就是本次程序的源代码了，下面就是本人自己的感悟以及思路了。

华丽的分割线

首先本次我们采取的是回溯法

我定义了三个不同的模块去实现

首先是十皇后的位置判断

我们都知道皇后问题要求，无论是n*n的皇后，他们必须保持在自己的攻击路线上面（接下来我们统称米字）不能出现别的皇后

也就是说其实每行都会有一个皇后，

所以我对所有皇后的位置进行一次判断，再把每个皇后的位置进行十次推演

void enumQueention(int queenArr[],int &nSolution)
{
for (queenArr[0] = 0; queenArr[0] < 10 ; queenArr[0]++)
for ( queenArr[1] = 0; queenArr[1] < 10; queenArr[1]++)
for (queenArr[2] = 0; queenArr[2] < 10; queenArr[2]++)
for (queenArr[3] = 0; queenArr[3] < 10; queenArr[3]++)
for (queenArr[4] = 0; queenArr[4] < 10; queenArr[4]++)
for (queenArr[5] = 0; queenArr[5] < 10; queenArr[5]++)
for (queenArr[6] = 0; queenArr[6] < 10; queenArr[6]++)
for (queenArr[7] = 0; queenArr[7] < 10; queenArr[7]++)
for ( queenArr[8] = 0; queenArr[8] < 10; queenArr[8]++)
for ( queenArr[9] = 0; queenArr[9] < 10; queenArr[9]++)
{
//判断当前方案是否有效
if (isClash(queenArr))
{
continue;
}
else
{
nSolution++;
//当前方案ok，打印方案出来
showQueens(queenArr, 10, nSolution);
}
}
}

方法有点笨，原谅本人脑子不好使，只能是这样啦

然后通过另一个模块的判断，我们去获取得到除第一个皇后其他皇后不会出现和第一个皇后路线重复或者出现在前一个皇后的米字路线上面

所以我通过对前一个皇后和后面皇后的位置进行判断

上图假设就是两个皇后的位置，

首先我们对两个皇后的x轴和y轴进行获取，当第一个皇后的 x-y 的位置等于当前皇后的 x-y 的位置时，那么他们构成等腰三角形，

我们知道，在皇后问题中，米字除了纵向和横向，还有两条线，两条线构成的角度为45度 而等腰三角形的角度是45度，如果构成的话

则表示该皇后现在的位置不能被放下，因为他处于前一个皇后或者其他皇后的米字路线上面

下面直接上代码：

bool isClash(int queenArr[])
{
for (int i = 1; i <= 10; i++)
{
for (int  j = 0;  j <= i-1;  j++)
{
if (queenArr[i] == queenArr[j])
{
//如果两个相等，两个则在同一列
return true;
}
if (abs(queenArr[i] - queenArr[j]) == abs(i-j))
{
return true;
}
}
}
return false;
}

进行判定之后我们进行一个返回值，然后在判断函数内部进行判断，如果返回为true，我们就继续循环，通过回溯每个皇后的位置进行判定

然后就是输出皇后位置的地方了

直接上代码：

/***********************************
*地图形式来打印皇后的位置
************************************/
void showQueens(int queenArr[], int nLen,int nSoLution)
{
printf("===========皇后解法第%d=============n",nSoLution);
for (int i = 0; i < nLen; i++)
{
//打印皇后前面的部分
if (queenArr[i] == -1)
{
for (int j = 0; j < nLen; j++)
{
printf("○");
}
printf("n");
continue;
}
//打印皇后前面的空余部分。。。
for (int j = 0; j < queenArr[i]; j++)
{
printf("○");
}
printf("●");//打印皇后
for (int j= 0; j< nLen - queenArr[i] - 1; j++)
{
//打印皇后后面的空余部分
printf("○");
}
printf("n");
}
printf("===============================n");
}

我们采用地图的形式进行输出，最后得出的效果如下：

十皇后的解决方法一共有724种；

八皇后的解决方法则是有92种；

本次学习通过对本算法的了解，再次加深了对C++的理解

特此记录，以防忘记；

2018.06.21

       Higanbana 

最后

以上就是有魅力毛豆最近收集整理的关于八皇后回溯法结题思路（C++）的全部内容，更多相关八皇后回溯法结题思路（C++）内容请搜索靠谱客的其他文章。