文章的后面是我最开始的想法，不巧妙，有点过于笨拙了，实现起来不好弄。
但是里面的一些想法还是不错的。
重新来看这道题，怎样简化一些：
- 首先我们真的需要一个矩阵吗？我之所以没做下去就是因为给我一个矩阵我不知道咋用啊！
其实，我们用矩阵是因为我们要在矩阵里面储存变量的值啊，而这里面，你建立了矩阵后储存什么呢？棋子是否在那个位置用矩阵也太浪费了吧！
所以简单一点，我们表示棋子在每一行/列的位置就行了，所以一维数组就搞定了。
因此，我们定义一个长度为8的数组，每个数组元素的值代表这一行/列棋子的位置，因此值的范围也在0-7
-
然后，我们发现这8个棋子不可能在同一行列，所以棋子的值肯定是0-7每个值对应一个
-
然后就是判断是否符合结果了，和之前一样我们只能用暴力的方法，判断每一种情况
这里和之前一样写一个判断的函数就好，不过很明显我们不需要判断横向纵向的情况，只需要看对角线。 -
那么有多少种情况呢？
也就是求所有的全排列嘛
全排列
那么怎么实现求这个排列呢？
- 就跟之前求字符的全排列一样，我们用的是递归的解法
void Permutation(char* pStr, char* pBegin)
{
if (!pStr || !pBegin)
return;
// if pBegin points to the end of string,
// this round of permutation is finished,
// print the permuted string
if (*pBegin == '\0')
{
printf("%s\n", pStr);
}
// otherwise, permute string
else
{
for (char* pCh = pBegin; *pCh != '\0'; ++pCh)
{
// swap pCh and pBegin
char temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
Permutation(pStr, pBegin + 1);
// restore pCh and pBegin
temp = *pCh;
*pCh = *pBegin;
*pBegin = temp;
}
}
}
具体的这个函数先不介绍，下次单独说
step2 实现
#include <iostream>
int count = 0;//存储当前解的个数
void arr_swap(int*arr,int a, int b)
{
int tmp = arr[a];
arr[a] = arr[b];
arr[b] = tmp;
}
bool queen_conflic(int* arr, int len)
{
for (int i = 0; i < len; i++)
{
for (int j = i + 1; j < len; j++)
{
if (arr[i] - arr[j] == j - i || arr[j] - arr[i] == j - i)
return true;
}
}
return false;
}
void print_arr(int* arr, int len)
{
std::cout << "solution_" << count<<":" << std::endl;
for (int i = 0; i < len; i++)
std::cout << arr[i] << " ";
std::cout << std::endl;
}
void permutation(int *arr, int len, int index)
{
if (index == len)
{
if (!queen_conflic(arr, len))
{
++count;
print_arr(arr, len);
}
}
else
{
for (int i = index; i < len; i++)
{
arr_swap(arr, i, index);
permutation(arr, len, index + 1);
arr_swap(arr, index, i);
}
}
}
void eightQueen()
{
const int queens = 8;
int arr[queens];
for (int i = 0; i < queens; i++)
{
arr[i] = i;//eight different values
}
permutation(arr, queens, 0);
}
int main()
{
eightQueen();
}
结果：
运算结果（部分）
wiki上说有12个独立解。但是总的解数是92个，因为包含了一些旋转的情况。
下面是我几天前尝试着做的时候的想法，显然我原本的想法失败了，因为思路还不是很清晰
额。。这个算法问题应该说很多人都听说过甚至都做过了，但是我直到今天才认真的思考这个问题，原因之一是因为，之前我一直觉得，这个可能很难。。当然现在我才刚刚审题，我决定写一下我的思路。
首先，我想到用一个8x8的矩阵表示坐标，然后假定我们得到了8个坐标
要判断是否会被吃掉，就是判断是否所有的棋子都满足：
1，不在同一条直线上
2，不在同一条斜线上
而直线和斜线都对应着两种情况
我想先写一个判断两个棋子坐标的函数：
struct point
{
int x;
int y;
};
//to judge
bool StraightLine(point* p1, point* p2)
{
return (p1->x == p2->x || p1->y == p2->y);
}
bool CrossLine(point* p1, point* p2)
{
return (abs(p1->x - p2->x) == abs(p1->y - p2->y));
}
bool conflict(point*p1, point*p2)
{
return (StraightLine(p1, p2) || CrossLine(p1, p2));
}
现在就可以判断两颗棋子是否符合要求了。
但是有8颗棋子，怎么处理呢？两两组合的话情况有很多。。？
--这里的话，可以用两层循环来对所有的两两组合判断
这样貌似有点复杂，走不通，再想想。。
- 首先我们每一列/每一行都需要放置一个棋子
那先在第一行假设一个位置，这个确定之后就会排除掉剩下的位置，我们第二行也确定一个，假设我们从第一个开始试，用上面的判断条件，如果满足则继续第三层。。。最后如果第8层也满足的话，这就是一种符合的思路
听起来还可以，我试试
文章参考何海涛大神文章
网友评论