n_queens.cpp

一个解决国际象棋中的八皇后问题的回溯算法.

// N_Queens.cpp: implementation of the N_Queens class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "N_QueensDemo.h"
#include "N_Queens.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

N_Queens::N_Queens()
{
	m_n = DEFAULT_NUM;
	m_v = new int[m_n];
	m_flag = false;

	for(int i=0; i<m_n; i++)
	{
		m_v[i] = -1;
	}
}

N_Queens::~N_Queens()
{
	if(m_v != NULL)
	{
		delete []m_v;
		m_v = NULL;
		m_n = 0;
	}
	m_flag = false;
}

N_Queens::N_Queens(int n)
{
	m_n = n;
	m_v = new int[m_n];
	m_flag = false;

	for(int i=0; i<m_n; i++)
	{
		m_v[i] = -1;
	}
}

bool N_Queens::Check(int k)
{
	for(int i=0; i<k; i++)
	{
		if(m_v[k] == m_v[i])
		{
			return false;
		}
		if((m_v[k]-m_v[i] == k-i) || (m_v[k]-m_v[i] == i-k))
		{
			return false;
		}
	}
	return true;
}

// 回溯法	
void N_Queens::N_QueensIter()
{
	int k = 0;
	while( k >= 0 )
	{
		while( m_v[k] < m_n-1 )
		{
			m_v[k]++;
			if( Check(k) )
			{
				if(k == m_n-1)
				{
					m_flag = true;
					return ;
				}
				else
				{
					k++;
				}
			}
		}
		m_v[k] = -1;
		k--;
	}
}

/////////////////////////////////////////////////////////////////////////////