queen.cpp

在一个8×8国际象棋盘上

/*==================Promgram Descrition================*/
/*程序名称：queen.cpp                                  */
/*程序目的：运用递归来解N皇后问题                      */
/*Written By Huaying                                   */
/*=====================================================*/

#include<iostream>
using namespace std;
char Chessboard[ 8 ][ 8 ];
int QueenPlace( int , int );

/*-----------------------------------------------------*/
/*递归解N皇后问题                                      */
/*-----------------------------------------------------*/
int N_Queens( int LocX, int LocY, int Queens)
{
	int i, j;      //循环计数变量
	int Result = 0; 
	
	if ( Queens == 8 )  // 递归结束条件
		return 1;
	else 
		if ( QueenPlace( LocX, LocY ) )
		{
			Chessboard[ LocX ][ LocY ] = 'Q';
			for ( i = 0; i < 8; i++)
				for( j = 0; j < 8; j++)
				{
					Result += N_Queens( i, j, Queens + 1 );
					if ( Result > 0 )
						break;
				}
			if ( Result > 0 )
				return 1;
			else
			{
				Chessboard[ LocX ][ LocY ] = 'X';
				return 0;
			}
		}
		else
			return 0;
}

//-----------------------------------------------
//判断传入坐标是否可放置皇后
//-----------------------------------------------
int QueenPlace(int LocX, int LocY)
{
	int i, j;
	
	if ( Chessboard[ LocX ][ LocY ] != 'X' )   //判断是否有皇后
		return 0;

	for ( j = LocY - 1; j >= 0; j-- )          //判断上方是否有皇后
		if ( Chessboard[ LocX ][ j ] != 'X' )
			return 0;
    
    for ( j = LocY + 1; j < 8; j++ )           //判断下方是否有皇后
		if ( Chessboard[ LocX ][ j ] != 'X' )
			return 0;

    for ( i = LocX - 1; i >= 0; i-- )          //判断左方是否有皇后
		if ( Chessboard[ i ][ LocY ] != 'X' )
			return 0;

    for ( i = LocX + 1; i < 8; i++ )          //判断右方是否有皇后
		if ( Chessboard[ i ][ LocY ] != 'X' )
			return 0;

    i = LocX - 1;
	j = LocY - 1;
    while ( i >= 0 && j >= 0 )                 ////判断左上方是否有皇后
		if( Chessboard[ i-- ][ j-- ] != 'X')
			return 0;

    i = LocX + 1;
	j = LocY - 1;
    while ( i < 8 && j >= 0 )                 ////判断左下方是否有皇后
		if( Chessboard[ i++ ][ j-- ] != 'X')
			return 0;

    i = LocX - 1;
	j = LocY + 1;
    while ( i >= 0 && j < 8 )                 ////判断右上方是否有皇后
		if( Chessboard[ i-- ][ j++ ] != 'X')
			return 0;
    
	i = LocX + 1;
	j = LocY + 1;
    while ( i < 8 && j < 8 )                 ////判断右下方是否有皇后
		if( Chessboard[ i++ ][ j++ ] != 'X')
			return 0; 
	return 1;
}

//-------------------------------------------------
//  主程序
//-------------------------------------------------
int main()
{
   int i, j;
   
   for ( i = 0; i < 8; i++ )
	   for ( j = 0; j < 8; j++ )
		   Chessboard[ i ][ j ] = 'X';
   N_Queens( 0, 0, 0 );

   cout << "The graph of 8 Queens on the Chessboard." << endl;
   cout << "      0   1   2   3   4   5   6   7   " << endl;
   cout << "    +---+---+---+---+---+---+---+---+ " << endl;

   for ( i = 0; i < 8; i++ )
   {
        cout << "  " << i << " |";
		for ( j = 0; j < 8; j++ )
			cout << "-" << Chessboard[ i ][ j ] << "-|";
		cout << "\n    +---+---+---+---+---+---+---+---+ " << endl;  
   }
}