問(wèn)題描述：

算法思想：

代碼實(shí)現(xiàn)：

#include

using namespace std;

class Queen

{

friend int nQueen(int);//求解八皇后

private:

bool place(int);//判斷落子是否合適

void backTrack(int);//回溯查找可行解

private:

int n;//皇后的個(gè)數(shù)

int *x;//當(dāng)前解

long sum;//當(dāng)前已找到的可行方案數(shù)

char **answer;//可行解

};

bool Queen::place(int k)

{

for(int i = 1; i < k; i++) if((abs(k-i) == abs(x[i]-x[k])) || (x[i] == x[k])) return false; return true; } void Queen::backTrack(int t) { if(t > n)

{

sum++;

cout<

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

{

for(int j = 1; j <= n; j++)

{

cout<

}

cout<

}

}

else

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

{

x[t] = i;

answer[t][i] = 'O';

if(place(t))

backTrack(t+1);

answer[t][i] = '+';

}

}

int nQueen(int n)

{

Queen queen;

queen.n = n;

queen.sum = 0;

int *p = new int[n+1];

//初始化可行解 answer = q

char **q = new char*[n+1];

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

q[i] = new char[n+1];

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

for(int j = 0; j <= n; j++)

q[i][j] = '+';

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

p[i] = 0;

queen.x = p;

queen.answer = q;

queen.backTrack(1);

delete[] p;

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

delete[] q[i];

delete[] q;

return queen.sum;

}

int main()

{

cout<> n;

int sumQueen = nQueen(n);

cout<

system("pause");

return 0;

}

喜歡 (0)or分享 (0)

總結(jié)

以上是生活随笔為你收集整理的c支限界算法语言n皇后问题分,算法(八)-回溯法-N皇后问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。