queenchess.cpp

queenchess类的测试函数, 求解八皇后问题,本程序给出了所有可能解.

// QueenChess类的定义

#include"queenchess.h"

// 构造函数，将棋盘初始化
QueenChess::QueenChess()
{
	solves = 0;
	int i = 0;
	for (; i < 8; ++i)
		chessState[i] = "--------";
}

// 打印成功的棋盘
void QueenChess::DrawChess() const
{
	int i, j;   
	cout << "\n 八皇后问题的第 " << solves << " 个解为： " << endl;
	cout <<"  0 1 2 3 4 5 6 7" << endl;
	for (i = 0; i < 8; ++i)
	{
		cout << i << " ";
		for (j = 0; j < 8; ++j)
			cout << chessState[i][j] << " ";
		cout << endl;
	}//end for 
	// 每打印一个成功的棋盘，暂停一下 
    system("pause"); 
}

// 求解八皇后问题，并给出放置成功的棋盘总个数	
void QueenChess::Solve()
{
	// 从第0行开始放置皇后
	PlaceQueen(0);
	cout << "\n八皇后问题总共的解个数为： " << solves << endl;
}

// 判断位置(row, col)是否是安全位置——即可以放置皇后而与前面放置的皇后不互相攻击
bool QueenChess::SafeJudge( int row, int col) const
{
	int qRow, qCol;
	// 检查前面各行，看与前面放置的皇后 是否发生攻击
	for (qRow = 0; qRow < row; qRow++)
	{
		string rowState = chessState[qRow];
		// 寻找第qRow行放置皇后的列数
		qCol = rowState.find("Q");
		// 如果两个皇后位于同一行、同一列或两条对角线上，则说明该位置不安全
		if (qRow == row || qCol == col    // 相同行或相同列
			|| (qCol-qRow) == (col-row) || (qCol+qRow) == (col+row) )  // 两条对角线上
			return false;
	}//end for
	return true;
}

// 在第row行的各列放置皇后
void QueenChess::PlaceQueen( int row)
{
	//穷尽第row行的所有列
	for ( int col = 0; col < 8; col++)
	{
		// 判断位置 (row,col) 是否安全
        if (SafeJudge(row,col))
        {
			// 位置(row, col)安全，则放一皇后
			chessState[row][col] = 'Q';
			// 若还没有放到第八行，则尝试下一行
			if ( row < 7)
			    PlaceQueen( row+1);
			// 已经放置了八个皇后，打印出成功的棋盘，并将解数加1
		    else 
			{
				solves++;
			    DrawChess();
			}
		}// end if
		//将该行的皇后取走，尝试下一列位置
        chessState[row] = "--------";
    }
}