#include < iostream>
#include < cmath >
#define maxSize 8 // 皇后数（行、列值）
#define Elemtpye int
using namespace std;

typedef struct{

Elemtpye data[maxSize];
int top;

}Stack;

// 初始化栈
void initStack(Stack &S) // !!要“& ”
{

S.top = -1;

}

// 判空
int empty(Stack S){

if(S.top == -1)
    return 1;
return 0;

}

// 判断栈满
int stackFull(Stack S)
{

if (S.top == maxSize-1)
	return 1;
return 0;

}

// 进栈
void push(Stack &S, Elemtpye e)
{

if(stackFull(S)){
    cout<<"The stack was full!"<<endl;	
    return;
}
S.data[++S.top] = e; 

}

// 出栈
void pop(Stack &S, Elemtpye &e)
{

if(empty(S)){
	cout<<"The stack was empty!"<<endl;
	return;
}
e = S.data[S.top--]; 

}

// 从栈底到栈顶依次输出数值（顺序输出）
void display(Stack S)
{

for(int i=0;i<=S.top;i++){
	cout<<S.data[i]<<" ";
}
cout<<endl;

}

// 判断该列能否放入皇后
int canput(Stack S,Elemtpye col)
{

for(int i=0;i<=S.top;i++){  // 和已存入的每一个元素进行比较 
	if(col==S.data[i] || abs(col-S.data[i])==abs(S.top+1-i))  // 属于同一列 或 属于同一对角线则退出（S.top+1 和 i 为行下标） 
	    return 0;
}	
return 1;

}

int main()
{

Stack s;
initStack(s);
int snum = 0;  // 解决方案个数
Elemtpye col = -1;  // 列的初始值设为-1；
while(1){
	++col;
	while(col<maxSize && !canput(s,col)){  // 找到符合的 col 的值 
		++col;
	}
	if(col<maxSize && !stackFull(s)) {  // 如果栈还没有满 
		push(s,col);
		if(stackFull(s)){   // 如果进栈后栈满，栈顶出栈 
			cout<<++snum<<" ";
			display(s);
			pop(s,col); 
		}
		else col = -1;  // 没有满，则下一行开始重新选列值, if else... 语句！！ 
	}
	if(col>=maxSize){
		if(empty(s)){   // 所有的都不符合 
			cout<<"There're no solutions anymore!"<<endl; 
			return 0;
		} 
		pop(s,col);  
	}
}  

}