Question

C++用栈结构实现八皇后问题

#include <iostream>
using namespace std;
const int StackSize=8;
int num=0;
template <class T>
class SeqStack
{
public:
SeqStack(){top=-1;}
void Push(T x);
void Pop();
void PlaceQueen(int row);
bool Judge();
void Print();
bool Empty(){if(top==-1) return true;else return false;};
private:
T data[StackSize];
int top;
};
template <class T>
void SeqStack<T>::Push(T x)
{
if(top>=StackSize-1) throw "上溢";
top++;
data[top]=x;
}
template <class T>
void SeqStack<T>::Pop()
{
if(Empty()) throw "下溢";
top--;
}
template <class T>
bool SeqStack<T>::Judge()
{
for(int i=0;i<top;i++)
if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))
return false;
return true;
}
template <class T>
void SeqStack<T>::PlaceQueen(int row)
{
for (int col=0;col<StackSize;col++)
{
Push(col);
if (Judge())
{
if (row<StackSize-1)
PlaceQueen(row+1);
else
{
num++;
Print();
}
}
Pop();
}
}
template <class T>
void SeqStack<T>::Print()
{
cout<<"NO."<<num<<":"<<endl;
for(int i=0;i<StackSize;i++)
{
for(int j=0;j<data[i];j++)
{
cout<<"□";
}
cout<<"■";
for(int j=StackSize-1;j>data[i];j--)
{
cout<<"□";
}
cout<<endl;
}
cout<<endl;
}
void main()
{
SeqStack<int> Queen;
Queen.PlaceQueen(0);
cout<<"总共有"<<num<<"种摆放方法。"<<endl;
}

以上为主程序。
在判断函数Judge中if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))这句话是判断是否在一列或者一斜线上的，问题我不明白的是data[i]和i的数值难道不一样么？判断是不是在一斜线上的哪句话始终没能理解，求助

Answer 1

关于...
data[top]==data[i] 判断是否在一列
(abs(data[top]-data[i]))==(top-i) 判断是否对角线

我觉得
i ＝ 0～7 可以理解为 是从上到下的第0～7行（共8行）。
data[i]，存储的是皇后的位置，i和data[i]是不一样的噢！
也就是说当data里存满8个数时，就是一种成功的摆法了，

比如看下面的‘第一种摆法’：

NO.1:
■□□□□□□□
□□□□■□□□
□□□□□□□■
□□□□□■□□
□□■□□□□□
□□□□□□■□
□■□□□□□□
□□□■□□□□

此时data里面的数是 { 0,4,7,5,2,6,1,3 }, 只记录皇后在每一行里的位置。

这样一来 皇后的位置 可以这样表现 ：（第i行, 第data[i]列）－－ 坐标点在左上角

再看top，这个算法的机制是，判断一个位置的时候，就压入这个位置（将它作为top），再与本身存在的皇后们比对位置。
当data[top]=data[i], ‘待评判的皇后’的列和以前某个皇后一样了，所以这个判断返回false

然后判断对角线，这道问题的解法很简洁，

将(top,data[top]), (i,data[i]) 这两个位置相比较
即 （第top行，第data[top]列）与 （第i行，第data[i]列）比较位置
top-i 表示：这两个位置相差多少行，
(data[top]-data[i]) 表示： 这两个位置相差多少列 （可能是负的）
abs()函数取绝对值
( abs(data[top]-data[i]) ) == (top-i)
如果 相距的行数 ＝ 相距的列数 ，那这两个位置就在对角线上，
不信你画你画下

－－－－－
啰嗦下,一般来说是这么判的（不管坐标点在哪个角, 下面以数学坐标轴为例）：
对于一个点 P1（x1,y1）和 P2(x2,y2)
如果 x1+x2 = x2+y2 , 表示沿正对角线冲突（左上到右下）
如果 x1-y2 = x2-y2 ,表示沿反对角线冲突（右上到左下）

看了半天我觉得您这个算法挺好的，学习了

Answer 2

if(data[top]==data[i]||(abs(data[top]-data[i]))==(top-i))

是判断 当前行放置的皇后 与 之前行的皇后是否在 同一竖线上 或者对角线上。

其中data数组存储的是 : data[i] 表示 第i行 的皇后放在 第 data[i] 列上。

另外喷我上面滴2货，这个方法很牛，用递归 是菜鸟的做法 ，写程序得注重效率。

Answer 3

他说用栈你就真用栈？？
其实你那个玩意用深度优先搜索完美替代，也没必要写栈，写个递归就好，你还写栈来模拟DFS实在有些无聊了。