其他
N 皇后问题的三种解法
(给算法爱好者加星标,修炼编程内功)
来源:IT修道者
https://blog.csdn.net/computerme/article/details/18080031
void queen(int row) {
if (n == row) //如果已经找到结果,则打印结果
print_result();
else {
for (k=0 to N) { //试探第row行每一个列
if (can_place(row,k) {
place(row,k); //放置皇后
queen(row+ 1); //继续探测下一行
}
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
const int N=20; //最多放皇后的个数
int q[N]; //各皇后所在的行号
int cont = 0; //统计解得个数
//输出一个解
void print(int n)
{
int i,j;
cont++;
printf("第%d个解:",cont);
for(i=1;i<=n;i++)
printf("(%d,%d)",i,q[i]);
printf("\n");
for(i=1;i<=n;i++) //行
{
for(j=1;j<=n;j++) //列
{
if(q[i]!=j)
printf("x");
else
printf("Q");
}
printf("\n");
}
}
//检验第i行的k列上是否可以摆放皇后
int find(int i,int k)
{
int j=1;
while(j<i) //j=1~i-1是已经放置了皇后的行
{
//第j行的皇后是否在k列或(j,q[j])与(i,k)是否在斜线上
if(q[j]==k ||abs(j-i)==abs(q[j]-k))
return 0;
j++;
}
return 1;
}
//放置皇后到棋盘上
void place(int k,int n)
{
int j;
if(k>n)
print(n);
else
{
for(j=1;j<=n;j++) //试探第k行的每一个列
{
if(find(k,j))
{
q[k] = j;
place(k+1,n); //递归总是在成功完成了上次的任务的时候才做下一个任务
}
}
}
}
int main(void)
{
clock_t start,finish;
int n;
printf("请输入皇后个数:");
scanf("%d",&n);
start = clock();
printf("\n使用非递归回溯法解决 %d 皇后问题时的运行情况\n",n);
place(1,n);
finish = clock();
printf("共有 %d 种不同的排列 计算用时%.2fms \n",count, (double) (finish - start));
system("pause");
return 0;
}
#include "iostream"
#include "cmath"
using namespace std;
#define Max 20 //定义棋盘的最大值
int a[Max];
int show(int S) //定义输出函数
{
int i,p,q;
int b[Max][Max]={0}; //定义并初始化b[][]输出数组
for(i=1;i<=S;i++) //按横列i顺序输出a[i]数组坐标
{
b[i][a[i]]=1;
printf("(%d,%d)\t",i,a[i]);
}
printf("\n");
for(p=1;p<=S;p++) //按棋盘的横列p顺序标明皇后的位置
{
for(q=1;q<=S;q++)
{
if(b[p][q]==1) //在第p行第q列放置一个皇后棋子
printf("●");
else
printf("○");
}
printf("\n");
}
return 0;
}
int check(int k) //定义check函数
{
int i;
for(i=1;i<k;i++) //将第k行与前面的第1~~k-1行进行判断
{
if((a[i]==a[k]) || (a[i]-a[k]==k-i) || (a[i]-a[k]==i-k)) //检查是否有多个皇后在同一条直线上
{
return 0;
}
}
return 1;
}
void check_m(int num) //定义函数
{
int k=1,count=0;
printf("Thepossible configuration of N queens are:\n");
a[k]=1;
while(k>0)
{
if(k<=num && a[k]<=num)//从第k行第一列的位置开始,为后续棋子选择合适位子
{
if(check(k)==0) //第k行的a[k]列不能放置皇后
{
a[k]++; //继续探测当前行的下一列:a[k]+1
}
else
{
k++; //第K行的位置已经确定了,继续寻找第k+1行皇后的位置
a[k]=1; //从第一列开始查找
}
}
else
{
if(k>num) //若满足输出数组的要求则输出该数组
{
count++;
printf("[%d]: ",count);
show(num); //调用输出函数show()
}
//如果k>num会执行下面两行代码,因为虽然找到了N皇后问题的一个解,但是要找的是所有解,需要回溯,从当前放置皇后的下一列继续探测
//如果a[k]>num也会执行下面两行代码,就是说在当前行没有找到可以放置皇后的位置,于是回溯,从上一行皇后位置的下一列继续探测
k--; //棋子位置不符合要求,则退回前一步
a[k]++; //继续试探下一列位置
}
}
printf("The countis: %d \n",count);
}
int main(void)
{
clock_t start,finish;
int n;
printf("请输入皇后个数:");
scanf("%d",&n);
start = clock();
printf("\n使用非递归回溯法解决 %d 皇后问题时的运行情况\n",n);
check_m(n);
finish = clock();
printf(" 计算时间%.2fms \n", (double) (finish - start));
system("pause");
return 0;
}
void test(int row, int ld, int rd)
{
int pos, p;
if( row != upperlim )
{
pos= upperlim & (~(row | ld | rd ));
while( pos )
{
p= pos & (~pos + 1);
pos= pos - p;
test(row| p, (ld | p) << 1, (rd | p) >> 1);
}
}
else
++ Ans;
}
#include "iostream"
using namespace std;
#include "time.h"
// sum用来记录皇后放置成功的不同布局数;upperlim用来标记所有列都已经放置好了皇后。
long sum = 0, upperlim = 1;
// 试探算法从最右边的列开始。
void test(long row, long ld, long rd)
{
if(row != upperlim)
{
//row,ld,rd进行“或”运算,求得所有可以放置皇后的列,对应位为0,
// 然后再取反后“与”上全1的数,来求得当前所有可以放置皇后的位置,对应列改为1
//也就是求取当前哪些列可以放置皇后
long pos = upperlim & ~(row | ld | rd);
while(pos) // 0 -- 皇后没有地方可放,回溯
{
//拷贝pos最右边为1的bit,其余bit置0
//也就是取得可以放皇后的最右边的列
long p = pos & -pos;
//将pos最右边为1的bit清零
//也就是为获取下一次的最右可用列使用做准备,
//程序将来会回溯到这个位置继续试探
pos-= p;
//row + p,将当前列置1,表示记录这次皇后放置的列。
//(ld + p) << 1,标记当前皇后左边相邻的列不允许下一个皇后放置。
//(ld + p) >> 1,标记当前皇后右边相邻的列不允许下一个皇后放置。
//此处的移位操作实际上是记录对角线上的限制,只是因为问题都化归
//到一行网格上来解决,所以表示为列的限制就可以了。显然,随着移位
//在每次选择列之前进行,原来N×N网格中某个已放置的皇后针对其对角线
//上产生的限制都被记录下来了
test(row+ p, (ld + p) << 1, (rd + p) >> 1);
}
}
else
{
//row的所有位都为1,即找到了一个成功的布局,回溯
sum++;
}
}
int main(int argc, char *argv[])
{
clock_tstart,finish;
int n;
printf("请输入皇后个数:");
scanf("%d",&n);
start= clock();
printf("\n使用位运算 %d 皇后问题的运行情况\n",n);
test(0, 0, 0);
finish= clock();
printf("共有%ld种排列, 计算时间%.2fms\n", sum, (double) (finish - start));
system("pause");
return 0;
}
所有下一个位置的试探过程都是通过位操作来实现的,这是借用了C语言的好处辅来实现的。
- EOF -
觉得本文有帮助?请分享给更多人
关注「算法爱好者」加星标,修炼编程内功
点赞和在看就是最大的支持❤️