当前位置:首页 » 操作系统 » 八皇后问题算法

八皇后问题算法

发布时间: 2023-07-31 04:13:07

Ⅰ 八皇后问题求解方法分类

八皇后问题
{
“八皇后”问题
递归法
求解
(
Pascal语言
)
八皇后问题是一个古老而着名的问题,是
回溯算法
的典型例题。该问题是十九世纪着名的数学家
高斯
1850年提出:在8X8格的
国际象棋
上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用
图论
的方法解出92种结果。现代教学中,把八皇后问题当成一个经典
递归算法
例题。
算法分析
:数组a、b、c分别用来标记冲突,a数组代表列冲突,从a[0]~a[7]代表第0列到第7列,如果某列上已经有皇后,则为1,否则为0;
数组b代表主对角线冲突,为b[i-j+7],即从b[0]~b[14],如果某条主对角线上已经有皇后,则为1,否则为0;
数组c代表从对角线冲突,为c[i+j],即从c[0]~c[14],如果某条从对角线上已经有皇后,则为1,否则为0;
另优化:第一个皇后在1~4格,最后*2,即为总解数
}
program
queens;
var
a:array
[1..8]
of
integer;
b,c,d:array
[-7..16]
of
integer;
t,i,j,k:integer;
procere
print;
begin
t:=t+1;
write(t,':
');
for
k:=1
to
8
do
write(a[k],'
');
writeln;
end;
procere
try(i:integer);
var
j:integer;
begin
for
j:=1
to
8
do
{每个皇后都有8种可能位置}
if
(b[j]=0)
and
(c[i+j]=0)
and
(d[i-j]=0)
then
{判断位置是否冲突}
begin
a:=j;
{摆放皇后}
b[j]:=1;
{宣布占领第J行}
c[i+j]:=1;
{占领两个对角线}
d[i-j]:=1;
if
i<8
then
try(i+1)
{8个皇后没有摆完,递归摆放下一皇后}
else
print;
{完成任务,打印结果}
b[j]:=0;
{回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
fillchar(a,sizeof(a),0);
{初始化数组}
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
try(1);{从第1个皇后开始放置}
end.
“八皇后”问题递归法求解
(c语言)
#i
nclude
"stdio.h"
static
char
Queen[8][8];
static
int
a[8];
static
int
b[15];
static
int
c[15];
static
int
iQueenNum=0;
//记录总的棋盘状态数
void
qu(int
i);
//参数i代表行
int
main()
{
int
iLine,iColumn;
//棋盘初始化,空格为*,放置皇后的地方为@
for(iLine=0;iLine<8;iLine++)
{
a[iLine]=0;
//列标记初始化,表示无列冲突
for(iColumn=0;iColumn<8;iColumn++)
Queen[iLine][iColumn]='*';
}
//主、从对角线标记初始化,表示没有冲突
for(iLine=0;iLine<15;iLine++)
b[iLine]=c[iLine]=0;
qu(0);
return
0;
}
void
qu(int
i)
{
int
iColumn;
for(iColumn=0;iColumn<8;iColumn++)
{
if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0)
//如果无冲突
{
Queen[iColumn]='@';
//放皇后
a[iColumn]=1;
//标记,下一次该列上不能放皇后
b[i-iColumn+7]=1;
//标记,下一次该主对角线上不能放皇后
c[i+iColumn]=1;
//标记,下一次该从对角线上不能放皇后
if(i<7)
qu(i+1);
//如果行还没有遍历完,进入下一行
else
//否则输出
{
//输出棋盘状态
int
iLine,iColumn;
printf("第%d种状态为:\n",++iQueenNum);
for(iLine=0;iLine<8;iLine++)
{
for(iColumn=0;iColumn<8;iColumn++)
printf("%c
",Queen[iLine][iColumn]);
printf("\n"screen.width/2)this.width=screen.width/2"
vspace=2
border=0>;
}
printf("\n\n"screen.width/2)this.width=screen.width/2"
vspace=2
border=0>;
}
//如果前次的皇后放置导致后面的放置无论如何都不能满足要求,则回溯,重置
Queen[iColumn]='*';
a[iColumn]=0;
b[i-iColumn+7]=0;
c[i+iColumn]=0;
}
}
}
八皇后的c语言解法:
#include
<stdio.h>
#include
<conio.h>
#include
<math.h>
int
n,k,a[20],num=0;
int
attack(int
k){
int
flag=0;
int
i=1;
while
((i<k)&&(a[k]!=a)&&(fabs(a[k]-a)!=(k-i)))
i++;
if
(i==k)
flag=1;
return
flag;
}
void
place(int
k)
{
//printf("
%d",k);
int
i;
if
(k==n+1){
num=num+1;
printf("num=%d:",num);
for
(i=1;i<n+1;i++)
printf("
%d",a);
printf("\n");}
else
{
for
(i=1;i<n+1;i++){
a[k]=i;
if
(attack(k)==1)
place(k+1);
else
a[k]=0;
}
}
}
main(){
scanf("%d",&n);
k=1;
place(k);
if
(k!=n+1)
printf("no
solution!\n");
getch();
}
n皇后问题(英文)http://mathworld.wolfram.com/QueensProblem.html

Ⅱ 如何用C语言编写八皇后问题

#include "stdio.h" x0dx0a#include "windows.h" x0dx0a#define N 8 /* 定义棋盘大小 */ x0dx0aint place(int k); /* 确定某一位置皇后放置与否,放置则返回1,反之返回0 */ x0dx0avoid backtrack(int i);/* 主递归函数,搜索解空间中第i层子树 */ x0dx0avoid chessboard(); /* 每找到一个解,打印当前棋盘状态 */ x0dx0astatic int sum, /* 当前已找到解的个数 */ x0dx0ax[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列 */ x0dx0aint main(void) x0dx0a{ x0dx0abacktrack(0); x0dx0asystem("pause"); x0dx0areturn 0; x0dx0a} x0dx0aint place(int k) x0dx0a{ x0dx0a/* 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。 x[j] == */ x0dx0a/* x[k] 时,两皇后在同一列上;abs(k - j) == abs(x[j] - x[k]) 时,两皇 */ x0dx0a/* 后在同一斜线上。两种情况两皇后都可相互攻击,故返回0表示不符合条件。*/ x0dx0afor (int j = 0; j < k; j ++) x0dx0aif (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0; x0dx0areturn 1; x0dx0a} x0dx0avoid backtrack(int t) x0dx0a{ x0dx0a/* t == N 时,算法搜索至叶结点,得到一个新的N皇后互不攻击的放置方案 */ x0dx0aif (t == N) chessboard(); x0dx0aelse x0dx0afor (int i = 0; i < N; i ++) { x0dx0ax[t] = i; x0dx0aif (place(t)) backtrack(t + 1); x0dx0a} x0dx0a} x0dx0avoid chessboard() x0dx0a{ x0dx0aprintf("第%d种解法:\n", ++ sum); x0dx0afor (int i = 0; i < N; i ++) { x0dx0afor (int j = 0; j < N; j ++) x0dx0aif (j == x[i]) printf("@ "); x0dx0aelse printf("* "); x0dx0aprintf("\n"); x0dx0a} x0dx0aprintf("\n"); x0dx0a}

Ⅲ 暴力穷举和回溯法(八皇后问题)

以前每次遇到算法问题都是直接暴力求解,一直以为自己用的是暴力穷举法,现在学了回溯法,发现部分问题其实使用的是回溯法,而不是单纯的暴力穷举。

例如求解一个n皇后问题:

1.使用暴力穷举,由于没有两个皇后能够放在一列上,那么解向量一定是数1,2,····,n的一个排列(第一行n种放法,第二行n-1种,以此类推)。时间复杂度O(n!).

为什么是一维而不是两维?因为没有两个皇后能在同一列,所以只用行标志就可以表示出皇后的位置,简化了问题

2.回溯法,就等于是一个一个的试,从1到n,时间复杂度O(n^n),每一行n种放法,总共n行。

看起来回溯法要比暴力穷举差很多,但是实际上回溯法很多时候实际算法复杂度并没有暴力穷举高。比如4皇后问题中,仅需要341个可能节点中的27个节点就可以找到解,但是暴力穷举实际会慢很多。

换一个思路,比如第一个皇后放在了0位置,暴力穷举第二个皇后放在1位置,那么之后的皇后无论怎么放都是错误的,也就是(n-2)!个向量全部都是错误的,而回溯法面对这种问题,会在之前就直接抛弃这种情况,速度会快很多。不要问为什么暴力穷举为什么不学回溯法那样提前抛弃,因为它是 暴力穷举 (这还算优化过一次,不然直接O(n^n))。

总而言之,回溯法并不需要得到所有情况,而且运行过程中会提前抛弃不合要求的情况,所以算法复杂度一般不会到最差的情况。

Ⅳ 八皇后究竟有多少种解法怎么解

八皇后问题是一个古老而着名的问题,是回溯算法的典型例题。该问题是十九世纪着名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线庆段上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象誉颂誉棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。 对于八皇后问题的实现,如果结合动态的图形演示,则可以使算法的描述樱猜更形象、更生动,使教学能产生良好的效果。下面是用Turbo C实现的八皇后问题的图形程序,能够演示全部的92组解。八皇后问题动态图形的实现

Ⅳ 八皇后问题算法详解

八皇后问题,是一个古老而着名的问题,是 回溯算法 的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯 认为有76种方案。1854年在柏林的扰游象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。

本文缓帆销的主要描述的是基于回溯算法轿备思想的求解算法,并尽可能在细节上给予读者直观展示,以使得读者可以有更好的理解。抛砖引玉,如有错误请不吝赐教。

算法的关键在于用一个二维数组chess [ ] [ ] 来记录每一个位置(第 i 行第 j 列)是否合法(行列对角线上没有填皇后,对应于数组 chess [ i ] [ j ] 为 0),用一个一维数Queenplace [ ] 组来记录每一行上皇后的列标(比如Queenplace [ row ] =column 表示第 row 行第 column 列填入皇后)。

行数 i 从第一行开始,遍历每一列 j ,如果chess [ i ] [ j ] 为0,那么说明此位置可以填入皇后,则将chess中与此位置同行同列同对角线的value自增 1 并且在 数组Queenplace 中记录相应的坐标。然后递归计算每一行直到最后一行成功填入皇后并在此时打印棋盘 。最后进行回溯,恢复chess [ ] [ ] ,将chess中与此位置同行同列同对角线的value自减 1 并继续进行下一列的计算。

热点内容
变量的存储分配 发布:2025-03-14 15:01:12 浏览:171
php的初始化 发布:2025-03-14 14:59:20 浏览:598
c语言链表数组 发布:2025-03-14 14:59:08 浏览:101
王者安卓区转苹果区会有什么变化 发布:2025-03-14 14:44:44 浏览:305
思迅收银系统数据服务器ip 发布:2025-03-14 14:44:35 浏览:473
商云x加密狗 发布:2025-03-14 14:44:28 浏览:670
如何快速清除手机图形密码 发布:2025-03-14 14:32:03 浏览:444
电子邮件账户的服务器该怎么填写 发布:2025-03-14 14:31:59 浏览:421
泰拉瑞亚蒲公英怎么开在线服务器 发布:2025-03-14 14:21:20 浏览:629
如何破坏门上的密码锁 发布:2025-03-14 14:19:39 浏览:968