回溯法之N皇后问题(从基数为0开始)

//回溯法之N皇后问题
//1.问题描述：在一个N*N的棋盘上放置N个皇后，且使得每两个之间不能互相攻击，也就是使得每两个不在同一行，同一列和同一斜角线上。
//2.设计思想与分析：
//基本思路：X(j)表示一个解的空间，j表示行数，里面的值表示可以放置在的列数，抽象约束条件得到能放置一个皇后的约束条件(1)X(i)!=X(k);(2)abs(X(i)-X(k))!=abs(i-k)。应用回溯法，当可以放置皇后时就继续到下一行，不行的话就返回到第一行，重新检验要放的列数，如此反复，直到将所有解解出。 
#include "stdafx.h"
#include <iostream>
using namespace std;
typedef int BOOL;
#define FALSE 0
#define TRUE 1
typedef void (__stdcall *PRINTQUEENS)(int* pnQueen, int nLen, int nIndex);
void __stdcall PrintQueens(int* pnQueen, int nLen, int nIndex)
{
	int i = 0;
	if ( (NULL == pnQueen) || (nLen <= 0) || (nIndex < 0))
	{
		cout << "err param!" << endl;
		return;
	}
	cout << "N皇后问题第" << nIndex << "个解:" << endl;
	for (i = 0; i < nLen; i++)
	{
		cout << pnQueen[i] << "\t";
	}
	cout << endl;
}
//检查是否可以放置一个新的皇后
BOOL IsQueenPlace(int* pnQueen, int nNewPlace)
{
	int i = 0;
	while (i < nNewPlace)
	{
		if ( (pnQueen[i] == pnQueen[nNewPlace]) || (abs(pnQueen[i] - pnQueen[nNewPlace]) == abs(nNewPlace - i)) )
		{
			return FALSE;
		}
		i++;
	}
	return TRUE;
}
BOOL NQueens(int nLen, PRINTQUEENS pfnPrint)
{
	if (nLen <= 3)
	{
		cout << nLen << "阶皇后问题无解!" << endl;
		return FALSE;
	}
	if (NULL == pfnPrint)
	{
		cout << "err param!" << endl;
		return FALSE;
	}
	int k = 0;
	int nIndex = 0;
	int* pnQueens = new int[nLen];
	if (NULL == pnQueens)
	{
		cout << "new memory failed!" << endl;
		return FALSE;
	}
	//从第一位开始遍历
	pnQueens[0] = 0;
	pnQueens[1] = 1;
	k = 1;
	while (k >= 0)
	{
		//pnQueens[k]++;
		while ( (pnQueens[k] < nLen) && (!IsQueenPlace(pnQueens, k)) )
		{
			pnQueens[k]++;
		}
		if (pnQueens[k] < nLen)
		{
			if ((nLen-1) == k)//找到了一组解
			{
				pfnPrint(pnQueens, nLen, nIndex);//打印结果
				nIndex++;
				k--;
				pnQueens[k]++;//同时+1
			}
			else
			{
				k++;
				pnQueens[k] = 0;
			}
		}
		else
		{
			k--; //没有合适的条件回溯
			pnQueens[k]++;//同时+1
		}
	}
	
	
	
	return TRUE;
}
int main(int argc, char* argv[])
{
	int nLen = 0;
	cout << "please input the number of queens: " << endl;
	cin >> nLen;
	NQueens(nLen, PrintQueens);
	return 0;
}