_queen.cpp

非递归实现N皇后问题求解

#include <iostream>
#include <stack>
#define N 8
using namespace std;

std::stack<int> st;

bool isValid(int pos)
{
	int size, i, b;
	stack<int> stcheck;
	stcheck = st;
    if (stcheck.empty())
		return false;
	size = stcheck.size();
	int& top = b;
	for (i=0;i<size;i++)
	{
		top = stcheck.top();
		if (pos==top || 
			top-stcheck.size()==(size+1)-pos || 
			top+stcheck.size()==(size+1)+pos)
		{
			return false;
		}
		stcheck.pop();
		
	}
	return true;
}

void Print()
{
	stack<int> stprint;
	stprint = st;
	int i, j, b;
	int &top = b;
	for (i=0;i<N;i++)
	{
		for (j=0;j<N;j++)
		{
			top = stprint.top();
			stprint.pop();
			if (j!=top)
				cout<<'□';
			else
				cout<<'■';
		}
		cout<<endl;
	}
	cout<<endl;
}

void main()
{
	int i, a, b;
	int &top = b;
	st.push(0);
	for (i=1;i<N;i++)
	{
		a = i;
		if (isValid(a))
		{
			st.push(a);
			continue;
		}
		else
		{
			if (i==N-1)//confliction in the last row
			{
				top = st.top();
				st.pop();
				i = top;
				if(i==N-1)
				{
					top = st.top();
					st.pop();
					i = top;
				}
			}
			continue;
		}
		if (st.size()==3)
		{
			Print();
		}
	}
}