queen.h

n皇后问题求解(8<=n<=1000) a) 皇后个数的设定 在指定文本框内输入皇后个数即可,注意: 皇后个数在8和1000 之间(包括8和1000) b) 求解 点击<

#ifndef	QUEEN_JTWU_H
#define	QUEEN_JTWU_H

#include "stdafx.h"
#include <stdlib.h>
//using namespace std;

const int MAX_QUEEN = 1000;
const int max_output_count = 25;
CString		str_collision[max_output_count];

class Queen {
public:
	Queen();
	~Queen();
	void SetQueenCount(int nQueen);
	int  GetQueenCount();
	int  Solve(CStatic & m_static_out);
	bool IsSolved();
	int  GetQindexInColumn(int col);

private:
	void InitQueenBoard();
	int  RandomIndex(int max_count);
	int  cal(int bits);
	int  GetCollisionCount(int row, int col);
	void CalculateCollision(int col);
	int  GetMinIndex(int &count);		///current column;
	int  GetNextIndex(int count);	///next index with the same collision_count in current column

private:
	int	 queen_count;		///queen count in the board
	int  total_collision_count;	///total collision count in the board
	int  cur_index;		///the current index of the queen in current column
	int  min_index;		///the index of the position with min collision_count in current column
	int  next_index;	///the index of the next position with the same collision_count in current column
	int  cur_collision_count;
	int  min_collision_count;
	int  last_total_change_count;
	int  cur_total_change_count;
	int  qboard[MAX_QUEEN];
	int  collision_count[MAX_QUEEN];
	int  ew_q_count[MAX_QUEEN];		//queen count from east to west
	int  nesw_q_count[MAX_QUEEN*2];	//queen count from north-east to south-west
	int  nwse_q_count[MAX_QUEEN*2];	//queen count from south-west to north-east
	int  turn;
};

Queen::Queen() {
	queen_count = 0;
	total_collision_count = -1;
	cur_index = min_index = next_index = -1;
	cur_collision_count = min_collision_count = -1;
	last_total_change_count = cur_total_change_count = 0;
	for ( int i=0; i<MAX_QUEEN; i++ ) {
		qboard[i] = -1;
		collision_count[i] = -1;
		ew_q_count[i]=0;
		nesw_q_count[i] = 0;
		nesw_q_count[i+MAX_QUEEN] = 0;
		nwse_q_count[i] = 0;
		nwse_q_count[i+MAX_QUEEN] = 0;
	}
	turn = 0;
}

Queen::~Queen() {
	queen_count = 0;
	total_collision_count = -1;
	cur_index = min_index = next_index = -1;
	cur_collision_count = min_collision_count = -1;
	last_total_change_count = cur_total_change_count = 0;
	for ( int i=0; i<MAX_QUEEN; i++ ) {
		qboard[i] = -1;
		collision_count[i] = -1;
	}
	turn = 0;
}

void Queen::SetQueenCount(int nQueen) { queen_count = nQueen; }
int  Queen::GetQueenCount() { return queen_count; }

int  Queen::Solve(CStatic & m_static_out) {
	for ( int i=0; i<max_output_count; i++ ) 
		str_collision[i] = "";
	InitQueenBoard();

	while ( total_collision_count > 0 ) {
		for ( int column=0; column<queen_count; column++ ) {
			CalculateCollision(column);

			if ( (last_total_change_count+cur_total_change_count) > 0 ) {
				if ( min_collision_count < cur_collision_count ) { //min_index has least collision
					ew_q_count[cur_index]--;
					nesw_q_count[cur_index-column+queen_count-1]--;
					nwse_q_count[cur_index+column]--;

					qboard[column] = min_index;
					ew_q_count[min_index]++;
					nesw_q_count[min_index-column+queen_count-1]++;
					nwse_q_count[min_index+column]++;

					cur_total_change_count ++;
					total_collision_count -= 2*cur_collision_count;
					total_collision_count += 2*min_collision_count;
				}
			} else {//stay in the same status for too long time
				if ( min_collision_count < cur_collision_count ) { //min_index has least collision
					ew_q_count[cur_index]--;
					nesw_q_count[cur_index-column+queen_count-1]--;
					nwse_q_count[cur_index+column]--;

					qboard[column] = min_index;
					ew_q_count[min_index]++;
					nesw_q_count[min_index-column+queen_count-1]++;
					nwse_q_count[min_index+column]++;

					cur_total_change_count ++;
					total_collision_count -= 2*cur_collision_count;
					total_collision_count += 2*min_collision_count;
				} else { // break current status
					if ( turn == column ) {
						ew_q_count[cur_index]--;
						nesw_q_count[cur_index-column+queen_count-1]--;
						nwse_q_count[cur_index+column]--;

						qboard[column] = next_index;
						ew_q_count[next_index]++;
						nesw_q_count[next_index-column+queen_count-1]++;
						nwse_q_count[next_index+column]++;

						turn += RandomIndex(queen_count-1);
						turn = turn<queen_count ? turn : RandomIndex(queen_count-1);
						cur_total_change_count ++;
					}
				}
			}
			last_total_change_count = cur_total_change_count;
			cur_total_change_count = 0;
		}

		////////////////////// The following code just for window output /////////////
		CString str = "";
		str.Format(" Total: %d\n",total_collision_count);
		for ( int i=0; i<max_output_count-1; i++ ) {
			str_collision[i] = str_collision[i+1];
		}
		str_collision[i] = str;
		str = "";
		for ( i=0; i<max_output_count; i++ )
			str += str_collision[i];
		m_static_out.SetWindowText(str);
		////////////////////// The previous code just for window output /////////////

	}//while ( total_collision_count > 0 )
	return total_collision_count;
}

bool Queen::IsSolved() { return total_collision_count==0; }

int  Queen::GetQindexInColumn(int col) {
	return qboard[col];
}

void Queen::InitQueenBoard() {
	//randomly put the queen in the board.
	for ( int i=0; i<MAX_QUEEN; i++ ) {
		ew_q_count[i]=0;
		nesw_q_count[i] = 0;
		nesw_q_count[i+MAX_QUEEN] = 0;
		nwse_q_count[i] = 0;
		nwse_q_count[i+MAX_QUEEN] = 0;
	}
	turn = 0;

	for ( int column=0; column<queen_count; column++ ) {
		int therow = RandomIndex(queen_count-1);
		qboard[column] = therow;
		ew_q_count[therow]++;
		nesw_q_count[therow-column+queen_count-1]++;
		nwse_q_count[therow+column]++;
	}

	last_total_change_count = 0;
	cur_total_change_count = 0;
	total_collision_count = 0;

	for ( column=queen_count-1; column>=0; column-- ) {
		CalculateCollision(column);
		total_collision_count += cur_collision_count;
	}
}

int  Queen::RandomIndex(int max_count) {
	double rate = (double)rand()/(double)cal(sizeof(int)*4-2);
	return (int)(max_count*rate);
}

int Queen::cal(int bits) {
	int total = 1;
	int count = 1;
	for ( int i=0; i<bits; i++ ) {
		count = count*2;
		total += count;
	}
	return total;
}

int  Queen::GetCollisionCount(int row, int col) {
	int count = 0 ;
	///caculate		north-west ---> south-east   direction
	count += nesw_q_count[row - col + queen_count - 1];
	count += nwse_q_count[row + col];
	count += ew_q_count[row];
	if ( qboard[col]==row )
		count -= 3;
	return count;
}

void Queen::CalculateCollision(int col) {
	//modify index, collision_count, collision_count[] <- current column
	for ( int row_index = 0; row_index<queen_count; row_index++ ) {
		collision_count[row_index] = GetCollisionCount(row_index,col);
	}
	cur_index = qboard[col];
	cur_collision_count = collision_count[cur_index];
	min_index = GetMinIndex(min_collision_count);
	next_index = GetNextIndex(cur_collision_count);
}

int  Queen::GetMinIndex(int &count) {
	int temp_collision_count;
	int index =0;
	count = collision_count[index];
	for ( int row_index=1; row_index<queen_count; row_index++ ) {
		temp_collision_count = collision_count[row_index];
		if ( temp_collision_count < count ) {
			count = temp_collision_count;
			index = row_index;
		}
	}
	return index;
}

int  Queen::GetNextIndex(int count) {
	int index = cur_index;
	int temp_collision_count;
	index++;
	index = index<queen_count ? index : 0 ;
	temp_collision_count = collision_count[index];
	while ( temp_collision_count != count ) {
		index++;
		index = index<queen_count ? index : 0 ;
		temp_collision_count = collision_count[index];
	}
	return index;
}

/////////////////////// End of Implementation//////////////////////

#endif///:~QUEEN_JTWU_H