用C++如何实现八皇后问题

由于皇后的攻击范围特性，注定我们每行只能放下一个皇后，于是我们要做的只是逐行放下皇后。八皇后问题是回溯法的典型问题。这里我们用的方法很简单：

从第一行开始逐个检索安全位置摆放皇后，一旦有安全位置则考虑下一行的安全位置。如果发现某行没有安全位置，则返回上一行继续检索安全位置;如果发现在最后一行找到了安全位置则输出整个棋盘。

原理很简单，整个程序中表现了这个思想的函数是void Solve()
下面是实现的代码：

//C++实现八皇后问题代码
#include

#include

#include

const int N=8; // Of course we are able to solve the "N queens problem".

using namespace std;

class QueenChess

{

public:

QueenChess(); // To initialize the chessboard

void Solve(); // To solve the problem and calculate the number of solutions

private:

string chessBlank; // A row of blank chessboard. We use this to 'delete' the row we don't need. (in fact, we substitute the black row for the row we want to delete)

string chessState[N]; // The whole chessboard, which has N rows and N columns

int solves; // The number of solutions

bool SafeJudge(int row, int col) const; // To judge whether we can put our queen in a paiticular position (row, col)

void PlaceQueen(int row); // Put our queen in a safe place in a particular row

void DrawChess() const; // Draw the whole chessboard when we got a solution

};

QueenChess::QueenChess()

{

solves=0;

for (int i=0;i

{

chessBlank+="-"; // So, our original row is just like "--------"

}

for (int i=0; i

{

chessState[i]=chessBlank; // Then, it becomes N rows

}

}

void QueenChess::Solve()

{

PlaceQueen(0); // Start placing queens at the first row

cout

}

void QueenChess::PlaceQueen(int row)

{

for (int col=0;col

{

if (SafeJudge(row,col)==true) // If we find one

{

chessState[row][col]='Q'; // We change the '-' by 'Q'

if (row

{

PlaceQueen(row+1); // If we found a safe place in this row, we do the same in the next row

}

else // We place N queens in the chessboard successfully

{

solves++; // solves++

DrawChess(); // Everytime we got a solution, we output it

}

}

chessState[row]=chessBlank; // Backtracking method. If we failed the find a safe place in the nth row, we just clear this row and go back to the previous row. Then we will find a new safe place with a bigger No. of column. If we can't find such a place, just go back to a previous previous row.

}

}

bool QueenChess::SafeJudge(int row,int col) const

{

int rowChecker, colChecker; // Two variables for checking

for (rowChecker=0; rowChecker

{

string rowState=chessState[rowChecker]; // check the invaild region made by the queen of the rowCheckerth row

colChecker=rowState.find('Q'); // Use 'find' to get the number of column of the queen

if (row==rowChecker or col==colChecker or (rowChecker-colChecker)==(row-col) or (rowChecker+colChecker)==(row+col)) // Check whether the place is safe

{

//cout

cout

for (drow=0;drow

{

cout

}

int main()

{

QueenChess chess;

chess.Solve();

return 0;

}

原文地址：http://soft.chinabyte.com/database/383/12071383.shtml

有用  |  无用 取消

猜你喜欢