queens.h

优化皇后问题的代码

/////////////////////////////////////////////////////////////////////////////
//              Copyright (c) 10.2003 Lchrennew Personal.                  //
//                         All rights reserved.                            //
//              Lchrennew个人 版权所有 不得抄袭 违者必究                   //
/////////////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////////////
//						   Queens Problem Class							   //
//								皇后问题类								   //
/////////////////////////////////////////////////////////////////////////////

#ifndef QUEENS1_H
#define QUEENS1_H

#include "iostream.h"
#include "stdio.h"
#include "conio.h"
#include "time.h"

#include "sysinfo.h"

/////////////////////////////////////////////////////////////////////////////
//Definition of Standard Class <Queens>,designed by lchrennew              //
/////////////////////////////////////////////////////////////////////////////
class Queens
{
	public:
		Queens(int s);										//constructor
		~Queens(){delete [] Square;}						//distructor of Class Queen
		FILE *cfPtr;										//cfPtr = Queens.txt file pointer
		clock_t start,end;									//clock
		bool solve_from();									//solve from the current configuration
	private:
		int size;											//board size
		int count;											//step of Queens
		long int result;									//to record the numbers of results
		long int total;										//to get the total times of the visiting
		int *Square;										//This pointer is for the store structure
		int GetNextFreeCol(int the_row);					//get the next free square of row
		bool checkFree(int row1,int col1,int row2,int col2);//check if a square not in the guard of other Queens
		void print();										//print the current status
};

/////////////////////////////////////////////////////////////////////////////
//Queens::Queens                                                           //
/////////////////////////////////////////////////////////////////////////////
Queens::Queens(int s)
{
	size=s>0?s:8;											 //default size is 8*8
	Square=new int[size];									 //new storage array
	for(int i=1;i<size;i++)									 //initialize all node to -1(empty)
		Square[i]=-1;
	if(size%2)
	{
		Square[0]=(int)(size/2)-1;
		if(size>1)
			Square[1]=Square[0]+2;
	}
	else
		Square[0]=size/2-1;
															 //initialize the vars
	count=0;
	result=0;
	total=0;
	cout<<"\nReady to initialize a Queens Class for ["<<size<<"*"<<size<<"] chessboard!"<<endl;
															 //output the success message
	if((cfPtr = fopen("Queens.txt","a"))==NULL)
		cout<<"File could not be opened"<<endl;
	else
		fprintf(cfPtr,"Queens for [%d*%d] chessboard!\n===================\n",size,size);

	cout<<endl
		<<"Now starting to solve and save result log to \\Queens.txt..."<<endl
		<<endl
		<<"Please wait and it may take more than few minutes if the board is large!"<<endl;
		//<<"Press CTRL <C> to cancle all processes."<<endl<<endl;

}

/////////////////////////////////////////////////////////////////////////////
//Queens::GetNextFreeCol                                                   //
/////////////////////////////////////////////////////////////////////////////
int Queens::GetNextFreeCol(int the_row)
	/*
	pre: none
	post: return the next free column number

	usage: get the next free column of row the_row
	*/
{
	int value=Square[the_row]+1;							 //from current square[the_row]+1 to free value
	bool got=false;											 //for the last (value ++)==size the cycle will break, so it should be false, and now it is initialized to false
	for(value;(value<size)&&(!got);value++)					 //when not got and not reach up limited
	{
		for(
			int row=0;
			(row<the_row)&&(checkFree(row,Square[row],the_row,value));
			row++
			);												 //get the first unused free square
		got=(row==the_row);									 //if the value unexist, if should break the cycle before row increase to the_row;
															 //else the row should reach the_row
	}
	if(got)
		return value-1;										 //now,return value-1(because the last time of cycle has done value++ before break) if got
	else
		return -1;											 //else reset the square
}

/////////////////////////////////////////////////////////////////////////////
//Queens::checkFree                                                        //
/////////////////////////////////////////////////////////////////////////////
bool Queens::checkFree(int row1,int col1,int row2,int col2)
	/*
	pre: have a known square and have a target square
	post: return true if the target is in the guard of the known square

	usage: check if the target square is not in the guard of the known square
	*/
{
	int pri1,sla1,pri2,sla2;
		pri1=col1-row1;										 //primary diagonal of known square
		sla1=col1+row1;										 //slave diagonal of know square
		pri2=col2-row2;										 //primary diagonal of target square
		sla2=col2+row2;										 //slave diagonal of target square
		if((pri1==pri2)||(sla1==sla2)||(col1==col2))		 //not free
			return false;
	return true;											 //free
}

/////////////////////////////////////////////////////////////////////////////
//Queens::solve_from                                                       //
/////////////////////////////////////////////////////////////////////////////
bool Queens::solve_from ()
	/*
	pre: the storage array has been initialized or has in the processing
	post: return true if all valid path(es) have(has) been travelled, else return false

	usage: solve the problem of Queens
	*/
{
	Square[count] = GetNextFreeCol(count);					 //get next free square from current configuration
	if(Square[count]==-1)									 //if not get the next free sub path for current parent path
	{
		count--;											 //fall back
		if(count==-1)										 //if the count has been 0-1 (means that the first row has no any more valid path)
		{													 //so output the end result and return true (success)
			cout<<endl<<"There are(is) "<<result<<" result!"<<endl
				<<"And you have "<<total <<" times to get the value!"<<endl;
			
			end=clock();
			fprintf(cfPtr,"There is(are) %d result(s)!\nAnd you had %d times to get the value!\n\n",result,total);
			fprintf(cfPtr,"Time elasped %d milliseconds on %d MHz CPU.\n\n",end-start,(int)measure_clock_speed());
			fclose(cfPtr);

			cout<<"The log has been saved to c:\\Queens.txt, open it to see the RESULTS!"<<endl;

			cout<<"Time elasped "<<(end-start)<<" milliseconds on "<<measure_clock_speed()<<" MHz CPU."<<endl;

			cout<<"\nAll Done!\n"<<endl;
			return true;
		}
	}
	else
	{
		count++;											   //if got	go foreward one step and record one success
		total++;
		if(count==size)										   //if the path has been a full path (means that the current configuration is a solution)
		{
			result++;										   //record one record
			print();										   //output current configuration
			count--;										   //fall back to the top valid row so that to go next path
		}
	}
	return false;
}

/////////////////////////////////////////////////////////////////////////////
//Queens::print                                                            //
/////////////////////////////////////////////////////////////////////////////
void Queens::print ()
	/*
	pre: the storage array has been initialized
	post: print(save) the current array nodes (configuration of the chessboard)

	usage: print(save) configuration
	*/
{
	fprintf(cfPtr,"Sol[%d]:",result);
	for(int i=0;i<size;i++)
		fprintf(cfPtr,"[%d,%d] ",i+1,Square[i]+1);
	fprintf(cfPtr,"\n");
	if(size>1)
	{
		result++;
		fprintf(cfPtr,"Sol[%d]:",result);
		for(i=0;i<size;i++)
			fprintf(cfPtr,"[%d,%d] ",i+1,size-Square[i]);
		fprintf(cfPtr,"\n");
	}
}

#endif