八皇后问题求解方法分类
八皇后问题
{
“八皇后”问题
递归法
求解
(
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:arr***
[1..8]
of
integer;
b,c,d:arr***
[-7..16]
of
integer;
t,i,j,k:integer;
procedure
print;
begin
t:=t+1;
write(t,':
');
for
k:=1
to
8
do
write(a[k],'
');
writeln;
end;
procedure
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
i8
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;iLine8;iLine++)
{
a[iLine]=0;
//列标记初始化，表示无列冲突
for(iColumn=0;iColumn8;iColumn++)
Queen[iLine][iColumn]='*';
}
//主、从对角线标记初始化，表示没有冲突
for(iLine=0;iLine15;iLine++)
b[iLine]=c[iLine]=0;
qu(0);
return
0;
}
void
qu(int
i)
{
int
iColumn;
for(iColumn=0;iColumn8;iColumn++)
{
if(a[iColumn]==0b[i-iColumn+7]==0c[i+iColumn]==0)
//如果无冲突
{
Queen[iColumn]='@';
//放皇后
a[iColumn]=1;
//标记，下一次该列上不能放皇后
b[i-iColumn+7]=1;
//标记，下一次该主对角线上不能放皇后
c[i+iColumn]=1;
//标记，下一次该从对角线上不能放皇后
if(i7)
qu(i+1);
//如果行还没有遍历完，进入下一行
else
//否则输出
{
//输出棋盘状态
int
iLine,iColumn;
printf("第%d种状态为：n",++iQueenNum);
for(iLine=0;iLine8;iLine++)
{
for(iColumn=0;iColumn8;iColumn++)
printf("%c
",Queen[iLine][iColumn]);
printf("n"screen.width/2)this.width=screen.width/2"
vspace=2
border=0;
}
printf("nn"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
((ik)(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;in+1;i++)
printf("
%d",a);
printf("n");}
else
{
for
(i=1;in+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皇后问题（英文）
八皇后问题算法详解
八皇后问题，是一个古老而著名的问题，是 回溯算法 的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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 并继续进行下一列的计算。
八皇后问题的问题概述
八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。
八皇后问题最早是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出。之后陆续有数学家对其进行研究，其中包括高斯和康托，并且将其推广为更一般的n皇后摆放问题。八皇后问题的***个解是在1850年由弗朗兹·诺克给出的。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。1874年，S.冈德尔提出了一个通过行列式来求解的方法，这个方法后来又被J.W.L.格莱舍加以改进。
艾兹格·迪杰斯特拉在1972年用这个问题为例来说明他所谓结构性编程的能力。
八皇后问题出现在1990年代初期的著名电子游戏第七访客中。
关于8皇后问题和八皇后问题python的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。