『原创』算法#11 迭代回溯法求解N皇后

/*
* @file				IterativeBacktrackNqueens.cpp
* @brief			IteratorBacktrack's way
* @author			taoxiaoxiao
* @date				12-1-2014
*/
//迭代回溯法求解N皇后
//输出解决方案数和行列标（只打印第一个解决方案）
#include <iostream>
#include <cmath>
using namespace std;

#define MAXN 13

int x[MAXN+1], y[MAXN+1], n, sum;
bool isGo = false;

bool place(int k)
{
	for (int j = 1; j < k; ++j)
	{
		if (x[k] == x[j] || abs(x[k] - x[j]) == abs(k - j))
			return false;
	}
	return true;
}

void IteratorBacktrackNqueens()
{
	int k = 1;

	while (k > 0)
	{
		while (x[k] < n)
		{
			x[k] += 1;
			if (place(k))
			{
				if (k == n)
				{
					++sum;
					if (isGo == false)                                  //保存第一组数据
					{
						for (int i = 1; i <= n; ++i)
							y[i] = x[i];
						isGo = true;
					}	
				}
				else
				{
					k++;
					x[k] = 0;
				}
			}
		}
		--k;
	}
}

int main()
{
	system("title 迭代回溯法---Nqueens");
	system("color 0a");

	cin >> n;
	IteratorBacktrackNqueens();
	cout << sum << endl;
	for (int i = 1; i <= n; ++i)
		cout << i << " " << y[i] << endl;

	return 0;
}