queen.cpp

queens8皇后问题,经典的数据结构和算法问题,用c++实现,有详细的中文注释.

//8皇后问题，实现文件的存储
#include"fstream.h"
#include <iostream.h>
#include<stdio.h>
#include   <stdlib.h>
const int max_board=10;
int insert_count=0;//记录insert函数被调用的次数，调试用
int remove_count=0;//记录REMOVE函数被调用的次数
class Queens{
public:
    Queens(int size);//构造函数
	~Queens();//析构函数
    bool is_solved() const;
    void print();
    bool unguarded(int col) const;//判断
    void insert(int col);
    void remove(int col);
    int board_size;
	int count1;//记录打印的结果数
private:
    int count;
    bool queen_square[max_board][max_board];
	ofstream outfile;
	//二维数组棋盘，ture代表已经放置QUEEN
};
//*************************************************
Queens::Queens(int size)
{
	count1=0;
    board_size=size;
    count=0;
    for(int row=0;row<board_size;row++)
        for(int col=0;col<board_size;col++)
            queen_square[row][col]=false;
	outfile.open("outfile.txt");
	if(!outfile)
	{
		cout<<"unable to open the file "<<endl;
		exit(0);
	}
	else{
		outfile<<"the result is :"<<endl;
	}
}
Queens::~Queens()
{
	outfile.close();
}


//*************************************************
void Queens::insert(int col) //设置数组count行col列为true，计数器count加一
{
    queen_square[count++][col]=true;
	outfile<<"the insert place is "<<count<<' '<<col<<endl;
	insert_count++;
}
//*************************************************
bool Queens::is_solved() const
{
    return count==board_size;
}
//*************************************************
void Queens::remove(int col)//
{
    queen_square[--count][col]=false;
	remove_count++;
	outfile<<"the remove place is "<<count<<' '<<col<<endl;
}
//*******************打印解答***********************
void Queens::print() 
{
	outfile<<"been_solved "<<++count1<<endl;
    outfile<<endl;
    for(int row=0;row<board_size;row++)
    {
        for(int col=0;col<board_size;col++)
		{
			if(queen_square[row][col]) 
				outfile<<"■";
			else outfile<<"□";
		}
        outfile<<endl;
		
    }
}
//******************判断是否设防***********************
bool Queens::unguarded(int col) const
{
    int i;
    bool ok=true;
    for(i=0;ok && i<count;i++)
        ok=!queen_square[i][col];
    for(i=1;ok && count-i>=0 && col-i>=0;i++)
        ok=!queen_square[count-i][col-i];
    for(i=1;ok && count-i>=0 && col+i<board_size;i++)
        ok=!queen_square[count-i][col+i];
    return ok;
}
//*******************核心模块－递归***********************
void solve_from(Queens &configuration)
{
    if(configuration.is_solved())
	{
		configuration.print();
	}
    else
        for(int col=0;col<configuration.board_size;col++)
            if(configuration.unguarded(col))
            {
                configuration.insert(col);
                solve_from(configuration);
                configuration.remove(col);
            }
}
//********************主函数部分***********************
void main()
{
    int board_size;
    cout<<"what is the size of the board?"<<endl;
    cin>>board_size;
    if(board_size<0 || board_size>max_board)
        cout<<"The number must be between 0 and "<<max_board<<endl;
    else{
        Queens configuration(board_size);
        solve_from(configuration);
    }
	cout<<insert_count<<endl;//显示
	cout<<remove_count<<endl;
	getchar();
}