八皇后问题

八皇后问题

在棋盘上放置皇后，使得行、列、对角线只能有一个皇后。

Board类表示棋盘，Resolver类表示求解算法。

#include <iostream>
#include <cstring>

using namespace std;

class Board {
	public:
		Board(int n);

		Board() : Board(DEFAULT_BOARD_SIZE) { }

		int GetSize() { return m_size; }

		void Set(int i, int j);

		void Clear(int i, int j);

		bool HasQueen(int i, int j);

		bool Try(int i, int j);

		bool Reinit(int n);

		void Print();

		~Board();

	private:
		bool _valid(int i,int j);
		int m_size;
		int* m_board;
		const static int DEFAULT_BOARD_SIZE = 8;
};

/** --------------------------------- **/
Board::Board(int n){
	m_size = n;
	m_board = new int[n*n];
	memset(m_board, 0, sizeof(int)*n*n);
}

Board::~Board(){
	delete[] m_board;
}

bool Board::_valid(int i,int j) {
	if (i<0 || i>=m_size)
		return false;

	if (j<0 || j>=m_size)
		return false;

	return true;
}

bool Board::Reinit(int n) {
	delete[] m_board;

	m_size = n;
	m_board = new int[n*n];
	memset(m_board, 0, sizeof(int)*n*n);

	return true;
}

void Board::Print() {
	int i,j;

	for (i=0; i<m_size; i++)
		for (j=0; j<m_size; j++) {
			if (HasQueen(i,j))
				cout<<"("<<i<<","<<j<<")";
		}
		
	cout<<endl;	
}

void Board::Set(int i, int j) {
	if (_valid(i,j))	
		m_board[i*m_size+j] = 1;
}

void Board::Clear(int i, int j) {
	if (_valid(i,j))	
		m_board[i*m_size+j] = 0;
}

bool Board::HasQueen(int i, int j) {
	if (_valid(i,j))	
		return  (m_board[i*m_size+j] == 1);
	else
		return false;
}

bool Board::Try(int i, int j) {
	int t;

	if (!_valid(i,j))
		return false;	

	// row
	for (t=0; t<GetSize(); t++)
		if (HasQueen(i, t)) return false;

	// column
	for (t=0; t<GetSize(); t++)
		if (HasQueen(t, j)) return false;

	// diagonal
	for (t=0; t<GetSize(); t++) {
		if (HasQueen(t, i+j-t)) return false;
		if (HasQueen(t, t-i+j)) return false;
	}

	return true;
}

class Resolver {
	public:
		int Resolve(Board* p);
	private:
		void _resolve(Board* p, int row);
};

void Resolver::_resolve(Board*p, int row) {
	int c;

	// place the queen in row
	for (c=0; c<p->GetSize(); c++) {

		if (p->Try(row,c)) {
			// place the queen in (row,c)
			p->Set(row,c);

			if (row<p->GetSize()-1) // place reset queens
				 _resolve(p,row+1);
			else // all queens are placed
				p->Print();

			// search other resolves	
			p->Clear(row,c);
		}
	}
}

int Resolver::Resolve(Board* p) {
	_resolve(p, 0);
	return 0;
}

int main()
{
	Resolver* r = new Resolver;
	Board* b = new Board(8);
	r->Resolve(b);
	return 0;
}