八皇后问题是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，是回溯算法的典型案例。
问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
像这样的棋盘：
Queen
对棋盘行和列标号，可以使用 0~7 或 1~8，通过行数与列数进行加减计算，得到如下的内容：
Queen_leftLine.png
Queen_rightLine.png
行 - 列 和 行 +列，可以清晰的看到具有很明显的规律
行 - 列 ，红线的方向，从左到右，从上到下的斜线，取值范围 [-7 ， 7],，共15个元素
-7,-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6,7
行 +列，红线的方向，从左到右，从下到上的斜线，取值范围 [2 ， 16] 或 [0 ， 14] ，共15个元素
当列和行标号范围 "1~8"
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
当列和行标号范围 "0~7"
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14
解题方法 ：
注 ：此处使用行列的标号范围 "1~8"
设置数组，判断某位置是否处于一个安全的位置
1. 建立数组，并初始化
因为每种斜线最多有15种可能，行列最多只有8种可能
// 判断左斜线
int r[16] = { 0 };
// 判断左斜线
int l[16] = { 0 };
// 判断列
int h[8] = { 0 };
例如： 取 x = 4， y = 5 位置，其左斜线 -1 ，右斜线 9 ，列 4
由于数组初始化为0，当填入一行皇后，需要进行占位，利用行列号来修改数组位置的值，修改为1
左斜线(x-y)取值范围：[-7 , 7] ，因此在左斜线 x-y+8, 则对应数组 l[1] 到 l[15]
右斜线(x+y)取值范围：[2 , 16] ，因此在右斜线 x+y-1则对应数组 r[1] 到 r[15]
例如：取 x = 4， y = 5 位置，4-5=-1,4+5=9 ,因此 l[7]=1、r[8]=1
2. 创建数组保存每种情况 , 并统计数量
// 符合条件的数量
int n = 0;
int que[8] = { 0 };
创建一维数组，来存放每行皇后的位置，每个皇后的取值都不同，也就是取值由0到7
3. 创建函数，输出保存数组的情况
void Print()
// 输出
{
cout << "第"<<n << "种：" ;
for (int i = 0; i < 8; ++i)
{
cout << que[i] ;
}
cout << endl;
}
4. 设计递归函数
递归参数为行数
void Queen(int row = 0)
// 输入行数
{
// 函数出口
if(row > 7)
{
n++;
Print();
return;
}
for (int i = 0; i < 8; ++i)
{
// 当一行到结尾，也没有找到解法，结束，返回上一行，
if(i>7)
{
return;
}
// 判断是否符合条件
if( !l[row-i+8] && !r[row+i-1] && !h[i])
{
// 符合条件保存该行的位置，并标记影响的斜线和列
que[row] = i;
h[i] = 1;
l[row-i+8] = 1;
r[row+i-1]= 1;
// 本行已找到，跳到下一行
Queen(row+1);
// 因为下一行没有找到位置，结束函数，此行该位置不能得到的结果，因此清除之前设置的内容
que[row] = 0;
l[row-i+8] = 0;
r[row+i-1]= 0;
h[i] = 0;
}
}
}
例子：
#include<iostream>
#include<string>
#include<stdlib.h>
using namespace std;
// 符合条件的数量
int n = 0;
// 数组存放每行皇后的位置
int que[8] = { 0 };
// 判断左斜线
int l[16] = { 0 };
// 判断左斜线
int r[16] = { 0 };
// 判断列
int h[8] = { 0 };
void Print()
// 输出
{
cout << "第"<<n << "种：" ;
for (int i = 0; i < 8; ++i)
{
cout << que[i] ;
}
cout << endl;
}
void Queen(int row = 0)
// 输入行数
{
// 每次递归结束的出口
if(row > 7)
{
// 完成一次递归，结果加一，并打印，结束递归
n++;
Print();
return;
}
for (int i = 0; i < 8; ++i)
{
// 当一行到结尾，也没有找到解法，结束，返回上一行，
if(i>7)
{
return;
}
// 判断是否符合条件
if( !l[row-i+8] && !r[row+i-1] && !h[i])
{
// 符合条件保存该行的位置，并标记影响的斜线和列
que[row] = i;
h[i] = 1;
l[row-i+8] = 1;
r[row+i-1]= 1;
// 本行已找到，跳到下一行
Queen(row+1);
// 因为下一行没有找到位置，结束函数，此行该位置不能得到的结果，因此清除之前设置的内容
que[row] = 0;
l[row-i+8] = 0;
r[row+i-1]= 0;
h[i] = 0;
}
}
}
int main(int argv,char* argc[])
{
Queen();
cout << n <<endl;
system("pause");
return 0;
}
N皇后问题
通过八皇后可以推出N皇后的问题的解决方案
主要问题在于斜线的区间和数量
注：行列的标号范围 "1~n"
当为N皇后，x+y的取值范围 [2 , 2n] , x-y 取值范围 [ 1-n , n-1 ] , 数量都为 2n-1
#include<iostream>
#include<cstdlib>
using namespace std;
template<int size>
class Queen
{
private:
int num = 0;
// 判断左斜线
int l[size*2] = { 0 };
// 判断左斜线
int r[size*2] = { 0 };
// 判断列
int h[size] = { 0 };
// 数组
int que[size] = { 0 };
public:
Queen(){};
~Queen(){};
public:
void check(int row = 0)
{
if(row >= size)
{
num++;
Prints();
return;
}
for (int i = 0; i < size; ++i)
{
if( !l[row-i+size] && !r[row+i-1] && !h[i])
{
que[row] = i;
h[i] = 1;
l[row-i+size] = 1;
r[row+i-1]= 1;
check(row+1);
// 因为下一行没有找到，因此此行该位置不能得到应有的结果，因此清空设置的内容
que[row] = 0;
l[row-i+size] = 0;
r[row+i-1]= 0;
h[i] = 0;
}
}
}
void Prints()
// 输出
{
cout << "第"<<num << "种：" ;
for (int i = 0; i < size; ++i)
{
cout << que[i] ;
}
cout << endl;
}
};
int main(int argc, char const *argv[])
{
Queen<8> Sir;
Sir.check();
system("pause");
return 0;
}
网友评论