8皇后问题是数据结构书中一个非常经典的题目。书中一般使用回溯法来解。回溯法一般要借助递归来实现，递归却又不是一下子想的清楚的，所以比较难理解。穷举法虽然算法效率不高，当输入很大时几乎不可能求解，但是却比较容易理解。下面就是实现的代码。为了易于实现，只把问题规模控制在4皇后上。
|
#include <iostream>
#include <cmath>
using namespace std;
void FourQueens()
{
for (int i = 1; i != 5; ++i)
{
for (int j = 1; j != 5; ++j)
{
for (int k = 1; k != 5; ++k)
{
for (int r = 1; r != 5; ++r)
{
if (i != j && j != k && k != r && k != i && r != i && r != j
&& abs(j - i) != 1 && abs(k - j) != 1 && abs(r - k) != 1-
n>
&& abs(k - i) != 2 && abs(r - i) != 3 && abs(r - j) != 2)
{
cout << i << " " << j << " " << k << " " << r << endl;
break;
}
}
}
}
}
}
int main()
{
FourQueens();
return 0;
} |
下面是严老师书上一副图，对理解上面的代码也很有帮助的。
下面也给出8皇后问题使用回溯法的代码：
|
#include <iostream>
#include <cmath>
using namespace std;
void PrintResult(int *arr, int n)
{
for (int i = 1; i != n + 1; ++i)
cout << "(" << i <<
"COLOR: #000000">"," << arr[i] << ")" << " ";
cout << endl;
}
bool Verify(int *arr, int i)
{
for (int k = 1; k != i; ++k)
if (arr[k] == arr[i] || abs(i - k) == abs(arr[i] - arr[k]))
return false;
return true;
}
void NQueens(int *arr, int i, int n)
{
for (int j = 1; j != n + 1; ++j)
{
arr[i] = j;
if (Verify(arr, i))
{
if (i == n)
PrintResult(arr, n);
else
NQueens(arr, i + 1, n);
}
}
}
int main()
{
int n;
cin >> n;
int *arr = new int[n&nb
sp;+ 1];
NQueens(arr, 1, n);
return 0;
}
|
