queens.cpp

八皇后问题的一个程序

//MY HONOUR IS MY LIFE!
//FOR GLORY!
// 我真诚地保证：
// 我自己独立地完成了整个程序从分析、设计到编码的所有工作。
// 如果在上述过程中，我遇到了什么困难而求教于人，那么，我将在程序实习报告中
// 详细地列举我所遇到的问题，以及别人给我的提示。
// 我的程序里中凡是引用到其他程序或文档之处，
// 例如教材、课堂笔记、网上的源代码以及其他参考书上的代码段,
// 我都已经在程序的注释里很清楚地注明了引用的出处。
// 我从未没抄袭过别人的程序，也没有盗用别人的程序，
// 不管是修改式的抄袭还是原封不动的抄袭。

// 我编写这个程序，从来没有想过要去破坏或妨碍其他计算机系统的正常运转。
    
// 0113325   杨剑锋




#include"Queens.h"
//#include<iostream>
#include<fstream.h>
#include<iostream.h>
#include<istream.h>
#include <strstrea.h>
//using namespace std;
ofstream myf("f:\\206\\yyx\\1.txt",ios::ate|ios::trunc);


Queens :: Queens(int size)
/* Post: TheQueens object is set up as an empty
  conguration on a chessboard with size squares in each
  row and column. */
{
  board_size = size;
  count = 0;
  m=0;
  
  for (int i = 0; i < board_size; i++)
	  col_free[i] = true;
  for (int j = 0; j < (2 * board_size - 1); j++)
	  upward_free [j] = true;
  for (int k = 0; k < (2 * board_size - 1); k++)
	  downward_free[k] = true;
}
void Queens :: insert(int col)
/* Pre: The square in the rst unoccupied row (row count ) and
  column col is not guarded by any queen.
  Post: A queen has been inserted into the square at row count and
?column col ; count has been incremented by 1. */
{
	queen_in_row[count]=col;
	col_free[col]=false;
	upward_free[count+col]=false;
    downward_free[count-col+board_size-1]=false;
	count++;
}
bool Queens :: unguarded(int col) const
/* Post: Returnstrue true or false according as the square in the first
   unoccupied row (row count ) and columncol is not guarded by any
   queen. */
{
	return col_free[col]
		&& upward_free[count+col]
		&& downward_free[count-col+board_size-1];
}
bool Queens :: is_solved()
{
	if(count==board_size){m++;return true;}
	else return false;
}
void Queens :: print()const
{  	
	
	for(int i=0;i<board_size;i++)
	{   
	
		for(int j=0;j<queen_in_row[i];j++)
		{  if((i+j)%2){cout<<"  ";
		myf <<"  ";}
		else
		{cout<<"N"<<" ";
		myf <<"N"<<" ";}
		}
		cout<<"Q"<<" ";
		myf <<"Q"<<" ";
		for(int k=queen_in_row[i];k<board_size-1;k++)
		{ if((i+k+1)%2){cout<<"  ";
		                myf <<"  ";}
		else
		{	cout<<"N"<<" ";
		myf <<"N"<<" ";}
		}
	
		cout<<endl;
		myf <<endl;

	}

	
	
	cout<<board_size<<"皇后第"<<m<<"种布局输出完毕"<<endl;//一个布局输出完，隔一行
	cout<<endl;
	myf <<board_size<<"皇后第"<<m<<"种布局输出完毕"<<endl;
	myf<<endl;
}
void Queens :: remove(int col)
{   count--;
    col_free[col] = true;
	upward_free [count+col] = true;
    downward_free[count-col+board_size-1] = true;
	
}
void Queens :: solve_from(Queens &configuration)
/* Pre: The Queens configuration represents a partially completed
   arrangement of nonattacking queens on a chessboard.
   Post: All n -queens solutions that extend the given configuration are
   printed. The configuration is restored to its initial state.
   Uses: The class Queens and the function solve_from , recursively. */
{  
   for (int col=0;col<configuration.board_size;col++)
   {if (configuration.unguarded(col))
			{
			 configuration.insert(col);
			 if (configuration.is_solved() ){configuration.print();}
			 else {solve_from(configuration);n++;}// Recursively continue to add queens.
			configuration.remove(col);
			}
   }
}
void main( )
/* Pre: The user enters a valid board size.
    Post: All solutions to the n-queens puzzle for the selected board size are
	printed.
	Uses: Theclass Queens and the recursive functionsolve from . */
{	
	int board_size;
		cout << "What is the size of the board? " <<flush;
	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);// Initialize empty conguration.
		n=0;
		configuration.solve_from(configuration);
		cout<<"共回溯了"<<n<<"步"<<endl;
		myf<<"共回溯了"<<n<<"步"<<endl;
	cout<<endl;
	
		// Find all solutions extending conguration.
	    }
}