Create by Yang
十行对我也太难了十行解法
题目描述
小灰图示
八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
分析
其实也是个递归的问题,并且可衍生出N皇后问题,思路就是要让计算机不停的尝试每个摆法,直到找到正确的方案。首先看皇后存在的条件:
一个皇后q(x,y)能被满足以下条件的皇后q(row,col)吃掉
- x=row(在纵向不能有两个皇后)
- y=col(横向)
- col + row = y+x;(斜向正方向)
- col - row = y-x;(斜向反方向)
本来想定义一个二维数组来表示棋盘,看了网上的解答后发现太过繁琐,直接用数组下标和value表示皇后的位置更为简便,之后学习了一个可读性比较好的解法。 - 首先定义两个全局变量
Queen
和Count
分别表示皇后和解的个数。 - 定义一个print函数将具体摆放位置打印出来
void print()
{
int outer, inner;
for (outer = 0; outer < 8; outer++) //打印8行
{
for (inner = 0; inner < Queen[outer]; inner++)
cout << "0 ";
cout << "1 "; //每行首个元素打印为1
for (inner = Queen[outer] + 1; inner < 8; inner++)
cout << "0 "; //打印后面7列
cout << "\n";
}
cout << "==================" << endl;
}
- 判断皇后位置的正确性,条件就是上面所说的4个条件
int is_true(int loop, int value)
{
int index, data; //相当于皇后的坐标(x, y)
for (index = 0; index < loop; index++)
{
data = Queen[index];
if (data == value)
{
return 0;
}
if ((index + data) == (loop + value))
{
return 0;
}
if ((index - data) == (loop - value))
{
return 0;
}
}
return 1;
}
- 最后是对皇后进行计算
void eight_queue(int index)
{
int loop;
//这里是用来构造八个皇后
for (loop = 0; loop < 8; loop++)
{
//用来判断第index个皇后在loop位置是否可行
if (is_true(index, loop))
{
//如果可行就将结构记录在这个全局数组中
Queen[index] = loop;
if (7 == index)
{
//打印并将全局变量增加一次
Count++;
print();
//将index这个皇后清空,方便下一次遍历
Queen[index] = 0;
return;
}
//这里使用了递归
eight_queue(index + 1);
//这里是回溯的思想,方便下一次遍历
Queen[index] = 0;
}
}
}