C/C++编程日记：八皇后问题解析（附代码）

#include

#include

#include

using namespace std;

class Queen

{

public:

int count;

Queen(int num);

~Queen();

void showQueen(int n);

void setQueen(int x,int y);

bool isClash();

bool checkClash(int nRow);

void enumQueenPostion(int &nSloution);

void putQueen(int nRow, int &nSloution);

private:

//每一个数组元素代表一个皇后的位置,queenArr[0] = 4;第一行第五格

int len;

int *queenArr;

};

Queen::Queen(int num)

{

this->len = num;

this->queenArr = (int*)malloc(sizeof(int)*num);

memset(this->queenArr,0,sizeof(int)*num);

}

Queen::~Queen()

{

delete[]queenArr;

}

//打印每一种可能情况

void Queen::showQueen(int n)

{

cout << "***************Queen position,sloution:"<= len || y < 0 || y >= len)

{

return;

}

queenArr[x] = y;

}

//判断冲突

bool Queen::isClash()

{

for (int i = 1; i <= len; ++i)

{

for (int j = 0; j <= i - 1; j++)

{

if (queenArr[i] == queenArr[j]) //说明在同一列相同值,不满足条件

{

return true;

}

if(abs(queenArr[i] - queenArr[j]) == abs(i - j)) //不可成45度角排列

{

return true;

}

}

}

return false;

}

//枚举法解决八皇后问题,枚举所有皇后可能所在的位置,将每一种可能情况列举出来

/*局限:

1.效率太低

2.不能解决n皇后问题

*/

void Queen::enumQueenPostion(int &nSloution)

{

for (queenArr[0] = 0; queenArr[0] < 8; queenArr[0]++)

for (queenArr[1] = 0; queenArr[1] < 8; queenArr[1]++)

for (queenArr[2] = 0; queenArr[2] < 8; queenArr[2]++)

for (queenArr[3] = 0; queenArr[3] < 8; queenArr[3]++)

for (queenArr[4] = 0; queenArr[4] < 8; queenArr[4]++)

for (queenArr[5] = 0; queenArr[5] < 8; queenArr[5]++)

for (queenArr[6] = 0; queenArr[6] < 8; queenArr[6]++)

for (queenArr[7] = 0; queenArr[7] < 8; queenArr[7]++)

{

count++;

if (isClash())

{

continue;

}

else

{

nSloution++;

showQueen(nSloution);

}

}

}

//检测当前当前行的状态

bool Queen::checkClash(int nRow)

{

for (int nColumn = 0; nColumn < nRow; nColumn++)

{

if (queenArr[nColumn] == queenArr[nRow])

{

return true;

}

if (abs(queenArr[nColumn] - queenArr[nRow]) == abs(nColumn - nRow))

{

return true;

}

}

return false;

}

//回溯法

void Queen::putQueen(int nRow,int &nSloution)

{

for (int i = 0; i < len; ++i)

{

queenArr[nRow] = i; //把循环放在当前循环的位置

//检查冲突

if (!checkClash(nRow))

{

if (nRow == len - 1)

{

nSloution++;

showQueen(nSloution);

}

else

{

//下一行位置

putQueen(nRow + 1,nSloution);

}

}

}

}

int main()

{

Queen queen(8);

//queen.setQueen(0,4);

//queen.setQueen(3,3);

//queen.setQueen(6,4);

int sloution = 0;

//queen.enumQueenPostion(sloution);

//queen.showQueen(sloution);

queen.putQueen(0,sloution);

return 0;

}