八皇后问题算法

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

八皇后问题
{
“八皇后”问题
递归法
求解
(
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 并继续进行下一列的计算。