/*
作者：臧旭
日期：2010/12/21
*/
#include "Queen.h"
#include <iostream>
using std::cout;
using std::endl;
#include <iomanip>
using std::setw;
using std::fixed;
Queen::Queen(int pN) {
n = pN;
stack = new Stack<int>(8);
}
void Queen::Solution() {
int i = 0;
int sum = 0;
//将第一行(1,1)的摆法先入栈
stack->Add(1);
int current = 2;
while (!stack->IsEmpty())
{
//探索下一行
for ( i = current; i <= n; i++ )
{
if (IsLegal(i)) break;
}
if (i <= n) // 找到了该层合法的摆法,并将该摆法入栈
{
stack->Add(i);
current = 1;
if(stack->GetSize() == n) //找到了一种摆法
{
sum++;
cout << "第" << sum << "种摆法:" << endl;
cout << *stack << endl;
current = i + 1; //下次继续从该层开始,位置为当前合法位置的下一个
stack->Delete(i);
}
}
else //如果未找到,则弹出上一层的摆法
{
current = *(stack->Delete(current));
current++;
if (stack->IsEmpty()) //如果把栈最下面一个位置弹出
{
if (current > 8) return;
else
{
stack->Add(current);
current = 1;
}
}
}
}
}
bool Queen::IsLegal(int k) {
int size = stack->GetSize();
int * temp = new int [size + 2];
bool isLegal = true;
int i = size;
//取出栈中的所有元素,并存入数组
while ( !stack->IsEmpty() )
{
int sulution;
sulution = *(stack->Delete(sulution));
temp[i--] = sulution;
}
//返还栈中的所有元素
for ( i = 1; i <= size; i++)
{
stack->Add(temp[i]);
}
//判断size+1层的当前摆法k是否合法 (i, temp[i]) 以及点 (size+1, k);
for ( i = 1; i <= size; i++)
{
if ( (abs(i - size - 1) == abs(temp[i] - k)) || (temp[i] == k))
{
isLegal = false;
}
}
delete [] temp;
return isLegal;
}
