N皇后问题专题
算法报告之Nqueen
1 问题重述
按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。
我们可以用回溯法解决N皇后问题，用数组模拟棋盘，从第一行开始，依次选择位置， 如果当前位置满足条件，则向下选位置，如果不满足条件，那么当前位置后移一位。
Int place（*x，n）函数用来判断皇后是否被攻击，其中数组x[]用来表示列数，n为皇后个数，判断的条件是(x[i]-x[n]==i-n‖x[i]-x[n]==n-i‖x[i]==x[n])； 初始化打印函数，相当于对棋盘初始化。将可以放皇后的位置记为1，不放的位置记为0； 在子函数Back（）中打印皇后解的空间； 求解过程中，如果满足一组可行解，则sum++。Int i=0，若x[i]>=n进行下一行，i++；当i=n时，sum++；输出该组可行解个数和位置矩阵，i–，回溯到上一层继续搜索可行解。 2.3代码实现
#include
using namespace std;
static int n,sum=0; //可行解个数
static int pos[20];
int place(int k)
{
//判断是否在一条线上，并返回0,1
for(int i=1;in){
sum++;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(jpos[i])
cout<<"*";
else
cout<<"Q";//如果已经安排完毕则输出棋盘和记录
}
cout<<endl;
}
printf("第%d种解法如上图所示: ",sum);
for(int i=1;i<=n;i++)
cout<<pos[i]<<" ";
cout<<endl<<endl<<endl;
}
else
{
//如果没有安排完则递归继续下一个安排，无解则返回上一个
for(int i=1;i>n;
printf("\n(Q表示皇后，*表示棋盘)\n\n\n");
Back(1);
printf("%d个皇后共有以上%d种解法\n\n\n",n,sum);
}
2.4 运行结果
这次用全排列来求了,横竖都不能相同,那么就是n个元素全排列的问题,然后从中找出对角线上也不符合的,剩下的就都符合了.
自己想了一个全排列的算法,不知道还有没有更高效的.原理是插入算法,每次插入,右边的元素右移,左边的不变,这个可以用过改下标数组来实现.然后,由于下标与元素的一一对应,元素的排列就等于下标的排列,不用再倒换过来了.
现在8皇后问题,考虑到对称性,可以下降到15毫秒了
#include
#include
#include
#include
#define maxsize 20+7
using namespace std;
int queen[maxsize];
int n;
int count_=0;
int main()
{
printf("请输入皇后数量N：");
scanf("%d",&n);
cout<<endl;
for(int i=0;i<n;i++)
{
// Init array
queen[i]=i;
}
do
{
// for(int i=0;i<n;i++)
// printf("%d\t",queen[i]);
// printf("\n");
// generate the permutation of queen
bool find=true;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if(j-i==abs(queen[j]-queen[i]))
{
// cout<< "false!!! " <<endl;
find=false;
break;
}
if(!find)
break;
}
}
// printf("\n");
if(find)
{
count_++;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(jqueen[i])
cout<<"*";
else
cout<<"Q";
}
cout<<endl;
}
printf("第%d种解法 ",count_);
// for(int i=0;i<n;i++)
// cout<<queen[i]<<" ";
cout<<endl<<endl<<endl;
}
}while(next_permutation(queen,queen+n));
printf("count:%d",count_);
return 0;
}
3.3运行结果
#include
#include
#include
#include
#define MaxSize 100000+7
#define maxsize 20+7
using namespace std;
int path[maxsize][maxsize];
int n;
int y_pos[maxsize];
int count=0;
bool judge(int num)
{
for(int i=0;itop=-1;
}
void DestroyStack(StType *&s)
{
free(s);
}
bool GetTop(StType *&s,Box &e)
{
if(s->top==-1)
return false;
e=s->data[s->top];
return true;
}
bool push(StType *&s,Box e)
{
if(s->top==MaxSize-1)
return false;
s->top++;
s->data[s->top]=e;
return true;
}
bool pop(StType *&s,Box &e)
{
if(s->top==-1)
return false;
e=s->data[s->top];
s->top--;
return true;
}
4.2运行结果
#include
using namespace std;
int board;
int n;
int ans = 0;
void n_queen(int col,int ld,int rd){
if(col == board){
ans++;
return;
}
int pos = board & (~(col | ld | rd));
while(pos){
int p = pos & (-pos);
pos = pos - p;
n_queen(col | p , (ld | p) <> 1);
}
}
int main(){
printf("请输入皇后数量N：");
cin>>n;
board = (1 << n) - 1;
clock_t ts=clock();
n_queen(0,0,0);
cout<<ans<<endl;
clock_t te=clock();
cout<<"共用时"<<te-ts<<"毫秒"<<endl;
}
5.2运行结果
6 总结
效率比较
| 算法 | 运行时间 |
|---|---|
| 递归回溯 | 629ms |
| 全排列 | 561ms |
| 栈 | 730ms |
从以上实验结果可以看出，在同样使用回溯法的情况下，基于位运算的解法大大地提高了求解速度，而且随着N值越大，求解速度提高的越多。
研究了两天各类八皇后写法，感觉自己对位运算的运用加深了一个层次，而且算法的设计如果能够遵循计算机的运行方式，将会获得更高的效率，更大的收获还是知道了自己的渺小，一个原以为十分简单的八皇后都可以衍生出这么多东西，递归的非递归的，全排列搜索的，回溯法的，甚至还有广搜版本的八皇后…
作者：清风er
