当前位置 博文首页 > 爱新觉罗?炒饭的博客：N皇后问题（子集树、排列树回溯法）
> 这题既可以采用子集树也可用排列树
问题描述
解向量
可行性约束
限界约束
代码一：子集树解决
#include <iostream>
using namespace std;
int x[100]; //皇后的位置(i,x[i]),即x[i]表示皇后在i行的列位置
int n; //棋盘规格
int sum = 0;
bool Place(int t) //实现限界约束判断
{
for (int i = 1; i <t;i++)
if(abs(x[t]-x[i])==abs(i-t)||x[i]==x[t])
return false;
return true;
}
void Backtrack(int t)
{
if(t>n)
{
sum++;
for (int i = 1; i <= n;i++)
cout << "(" << i << "," << x[i] << ")"
<< " ";
cout << endl;
}
else
{
for (int i = 1; i <= n;i++)
{
x[t] = i;
if(Place(t))
Backtrack(t + 1);
}
}
}
int main()
{
cout << "请输入棋盘规格或者皇后数量" << endl;
cin >> n;
for (int i = 0; i <= n;i++)
x[i] = 0;
Backtrack(1);
cout << sum << endl;
return 0;
}
代码二：排列树解决
#include <iostream>
using namespace std;
int x[100]; //皇后的位置(i,x[i]),即x[i]表示皇后在i行的列位置
int n; //棋盘规格
int sum = 0;
bool Place(int t) //实现限界约束判断
{
for (int i = 1; i < t;i++)
if(abs(i-t)==abs(x[i]-x[t])||x[i]==x[t])
return false;
return true;
}
void Backtrack(int t)
{
if(t>n)
{
sum++;
for (int i = 1; i <= n;i++)
cout << "(" << i << "," << x[i] << ")"
<< " ";
cout << endl;
}
else
{
for (int i = t; i <= n;i++)
{
swap(x[i], x[t]);
if(Place(t))
Backtrack(t + 1);
swap(x[i], x[t]);
}
}
}
int main()
{
cout << "请输入棋盘规格或者皇后数量" << endl;
cin >> n;
for (int i = 0; i <= n;i++)
x[i] = i;
Backtrack(1);
cout << sum << endl;
return 0;
}
