n皇后问题算法是
Ⅰ n皇后递归算法
就是深搜算法
代码如下：
var ans:array[1..13] of byte;
b,c,d:array[-12..26] of boolean;
n,i,max:longint;
procere print;
var i:longint;
begin
for i:=1 to n do
write(ans [i] ,' ');
writeln;
end;
procere gyw(i:integer);
var j:integer;
begin
if i>n then
begin
// print;
inc(max);
end
else for j:=1 to n do
if (b [j] =false)and(c[i+j]=false)and(d[i-j]=false) then
begin
ans [i] :=j;
b [j] :=true;
c[i+j]:=true;
d[i-j]:=true;
gyw(i+1);
b [j] :=false;
c[i+j]:=false;
d[i-j]:=false;
end;
end;
begin
read(n);
gyw(1);
writeln(max);
end.
Pascal的
Ⅱ 算法的n 皇后问题是否必然有解，理由是什么 研究好久到处爬文还是搞不太懂QAQ 谢谢！！
N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。
一、 求解N皇后问题是算法中回溯法应用的一个经典案例
回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。
在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。
下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘：
1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列
2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步
3) 在当前位置上满足条件的情形：
在当前位置放一个皇后，若当前行是最后一行，记录一个解；
若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；
若当前行是最后一行，当前列不是最后一列，当前列设为下一列；
若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；
以上返回到第2步
4) 在当前位置上不满足条件的情形：
若当前列不是最后一列，当前列设为下一列，返回到第2步;
若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;
算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。
在具体解决该问题时，可以将其拆分为几个小问题。首先就是在棋盘上如何判断两个皇后是否能够相互攻击，在最初接触这个问题时，首先想到的方法就是把棋盘存储为一个二维数组，然后在需要在第i行第j列放置皇后时，根据问题的描述，首先判断是在第i行是否有皇后，由于每行只有一个皇后，这个判断也可以省略，然后判断第j列是否有皇后，这个也很简单，最后需要判断在同一斜线上是否有皇后，按照该方法需要判断两次，正对角线方向和负对角线方向，总体来说也不难。但是写完之后，总感觉很笨，因为在N皇后问题中这个函数的使用次数太多了，而这样做效率较差，个人感觉很不爽。上网查看了别人的实现之后大吃一惊，大牛们都是使用一个一维数组来存储棋盘，在某个位置上是否有皇后可以相互攻击的判断也很简单。具体细节如下：
把棋盘存储为一个N维数组a[N]，数组中第i个元素的值代表第i行的皇后位置，这样便可以把问题的空间规模压缩为一维O(N)，在判断是否冲突时也很简单，首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等，即| row – i | = | col – a[i] | 。这样某个位置是否可以放置皇后的问题已经解决。
Ⅲ 算法 n皇后 求详细解答
Ⅳ 寻求八皇后的迭代算法解释。
也不知是不是你想要的解释，采用回溯法：（以前写的，直接粘贴……）
用一个函数来判断某个位置是否安全，安全的位置说明它所在的行、列和对角线上都没有放置皇后，因此不会出现皇后互相攻击的情况；否则该位置不安全。其具体实现的过程是找出所有放置过的皇后，将它们的位置与该位置进行比较判断。又注意到同一行最多只能放置一个皇后，因此，只需要对前面的各行逐行扫描皇后，就可以找出所有皇后的位置。
为便于显示，假设棋盘的状态为“-”时表示未放皇后状态，为“Q”时表示放置了皇后的状态。
//
判断位置(
row,
col
)是否是安全位置
bool
safeJudge(
int
row,
int
col
)
const
{
int
qRow,
qCol;
//
检查前面各行，看与前面放置的皇后是否发生攻击
for(
qRow
=
0;
qRow
<
row;
qRow++
)
{
string
rowState
=
chessState[
qRow
];
//
寻找第qRow行放置皇后的列数
qCol
=
rowState.find(
"Q"
);
//
判断是否安全
if(
qRow
==
row
||
qCol
==
col
||
(
qCol
-
qRow
)
==
(
col
-
row
)
||
(
qCol
+
qRow
)
==
(
col
+
row
)
)
return
false;
}
return
true;
}
试着先把第一个皇后放在棋盘上，然后再放第二个皇后，使两个皇后不会互相攻击，再放第三个皇后，使得它与前两个皇后都不会互相攻击，以此类推，直至所有的皇后都放上去。如果第七个皇后放上后，第八个皇后已经没有安全位置可以放置，则试着调整第七个皇后的位置，再尝试第八个皇后有没有安全位置；如果第七个皇后的所有安全位置都已尝试过了，第八个皇后还是没有安全位置，则试着调整第六个皇后的位置。如此类推，最糟糕的情况是一直到将第一个皇后的位置进行调整。由此可见，采用回溯法，过程的实现形式非常简单自然，然而这一过程的工作量非常大。
void
QueenChess::placeQueen(
int
row
)
{
//
穷尽第row行的所有列
for(
int
col
=
0;
col
<
8;
col++
)
{
if(
safeJudge(
row,
col
)
)
{
chessState[
row
][
col
]
=
"Q";
//
若还没有放到第八行，则尝试下一行
if(
row
<
7
)
placeQueen(
row
+
1
);
//
已经放置了八个皇后，打印出成功的棋盘，并将解数加1
else
{
solves++;
drawChess();
}
}
//
将该处的皇后取走，尝试下一列位置
chessState[
row
]
=
"--------";
}
}
这个算法能发现所有可能的解，不过它认为棋盘是具有行列编号的。事实上，棋盘并没有行列编号，如位置（0,0）和（7,7）其实是对称位置，因此这种算法给出的某些解也是对称的。为了便于理解，假设棋盘是具有行列编号的。
建立一个QueenChess类，见相应程序。
QueenChess::QueenChess()
{
solves
=
0;
for(
int
i
=
0;
i
<
8;
i++
)
chessState[
i
]
=
"--------";
}
void
QueenChess::drawChess()
{
int
i,
j;
cout
<<
"\n八皇后问题的第"
<<
solves
<<
"个解为："
<<
endl;
cout
<<
"
0
1
2
3
4
5
6
7"
<<
endl;
for(
i
=
0;
i
<
8;
i++
)
{
cout
<<
i
<<
"
";
for(
j
=
0;
j
<
8;
j++
)
cout
<<
chessState[
i
][
j
]
<<
"
";
cout
<<
endl;
}
system(
"pause"
);
}
void
QueenChess::solve()
{
//
从第0行开始放置皇后
placeQueen(
0
);
cout
<<
"\n八皇后问题总共的解的个数为："
<<
solves
<<
endl;
}
Ⅳ 求~~~pascal八皇后 非递归详细算法和程序
〖问题描述〗
在一个8×8的棋盘里放置8个皇后，要求每个皇后两两之间不相"冲"（在每一横列竖列斜列只有一个皇后）。
〖问题分析〗(聿怀中学吕思博)
这道题可以用递归循环来做，分别一一测试每一种摆法，直到得出正确的答案。主要解决以下几个问题：
1、冲突。包括行、列、两条对角线：
（1）列：规定每一列放一个皇后，不会造成列上的冲突；
（2）行：当第I行被某个皇后占领后，则同一行上的所有空格都不能再放皇后，要把以I为下标的标记置为被占领状态；
（3）对角线：对角线有两个方向。在同一对角线上的所有点（设下标为(i,j)），要么(i+j)是常数，要么(i-j)是常数。因此，当第I个皇后占领了第J列后，要同时把以(i+j)、(i-j)为下标的标记置为被占领状态。
2、数据结构。
（1）解数组A。A[I]表示第I个皇后放置的列；范围：1..8
（2）行冲突标记数组B。B[I]=0表示第I行空闲；B[I]=1表示第I行被占领；范围：1..8
（3）对角线冲突标记数组C、D。
C[I-J]=0表示第（I-J）条对角线空闲；C[I-J]=1表示第（I-J）条对角线被占领；范围：-7..7
D[I+J]=0表示第（I+J）条对角线空闲；D[I+J]=1表示第（I+J）条对角线被占领；范围：2..16
〖算法流程〗
1、数据初始化。
2、从n列开始摆放第n个皇后（因为这样便可以符合每一竖列一个皇后的要求），先测试当前位置(n,m)是否等于0（未被占领）:
如果是，摆放第n个皇后，并宣布占领(记得要横列竖列斜列一起来哦)，接着进行递归；
如果不是，测试下一个位置(n,m+1)，但是如果当n<=8,m=8时，却发现此时已经无法摆放时，便要进行回溯。
3、当n>;8时，便一一打印出结果。
〖优点〗逐一测试标准答案，不会有漏网之鱼。
〖参考程序〗queen.pas
----------------------------------------------------------------------------
programtt;
vara:array[1..8]ofinteger;
b,c,d:array[-7..16]ofinteger;
t,i,j,k:integer;
procereprint;
begin
t:=t+1;
write(t,'');
fork:=1to8dowrite(a[k],'');
writeln;
end;
proceretry(i:integer);
varj:integer;
begin
forj:=1to8do{每个皇后都有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;
ifi<8thentry(i+1){8个皇后没有摆完，递归摆放下一皇后}
elseprint;{完成任务，打印结果}
b[j]:=0;{回溯}
c[i+j]:=0;
d[i-j]:=0;
end;
end;
begin
fork:=-7to16do{数据初始化}
begin
b[k]:=0;
c[k]:=0;
d[k]:=0;
end;
try(1);{从第1个皇后开始放置}
end.
==========================================
这是N皇后问题，看看吧：
在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，问可能的方案及方案数。
const max=8;
var i,j:integer;
a:array[1..max] of 0..max; //放皇后数组
b:array[2..2*max] of boolean; // ‘/’对角线标志数组}
c:array[-(max-1)..max-1] of boolean;// ‘\’对角线标志数组}
col:array[1..max] of boolean; //列标志数组}
total:integer; //统计总数}
procere output; //这里是输出过程
var i:integer;
begin
write('No.':4,'[',total+1:2,']');
for i:=1 to max do write(a[i]:3);write(' ');
if (total+1) mod 2 =0 then writeln; inc(total);
end;
function ok(i,dep:integer):boolean; //判断第dep行第i列可放否？
begin
ok:=false;
if ( b[i+dep]=true) and ( c[dep-i]=true) {and (a[dep]=0)} and
(col[i]=true) then ok:=true
end;
procere try(dep:integer);
var i,j:integer;
begin
for i:=1 to max do //每一行均有max种放法，对吧？xixi~~~~
if ok(i,dep) then begin
a[dep]:=i;
b[i+dep]:=false; // ‘/’对角线已放标志
c[dep-i]:=false; // ‘\’对角线已放标志
col[i]:=false; // 列已放标志
if dep=max then output
else try(dep+1); // 递归下一层
a[dep]:=0; //取走皇后,回溯
b[i+dep]:=true; //恢复标志数组
c[dep-i]:=true;
col[i]:=true;
end;
end;
begin
for i:=1 to max do begin a[i]:=0;col[i]:=true;end;
for i:=2 to 2*max do b[i]:=true;
for i:=-(max-1) to max-1 do c[i]:=true;
total:=0;
try(1);
writeln('total:',total);
end.
Ⅵ n皇后问题，递归算法。
c:
#include<stdio.h>
#include<stdlib.h>
intresult=0;
voidqueen(int*chess,intlen,intn){
if(n==len){
result++;
}else{
intflag=0;
for(inti=0;i<len;i++){
flag=1;
for(intj=0;j<n;j++){
if(abs(n-j)==abs(i-chess[j])||chess[j]==i){
flag=0;
break;
}
}
if(!flag)
continue;
chess[n]=i;
queen(chess,len,n+1);
chess[n]=0;
}
}
}
intmain(void){
intn;
int*chess;
scanf("%d",&n);
chess=(int*)malloc(sizeof(int)*n);
queen(chess,n,0);
printf("result=%d ",result);
return0;
}
Ⅶ 利用《数据结构》课程知识完成C语言程序设计“N皇后问题”（堆栈，一维数组，普通算法都可以，用C语言写
#include<stdio.h>//N皇后问题
#include<
stdlib.h
>
#include<stdio.h>
#include<
iostream.h
>
#include<
time.h
>
#include<dos.h>
#include<malloc.h>
typedefstruct{
int*elem;
intlength;
intlistsize;
}Sqlist;
intInitList(Sqlist&L){//初始化
L.elem=(int*)malloc(100*sizeof(int));
if(!L.elem)
return0;
L.length=0;
L.listsize=100;
return1;
}
intInsert(Sqlist&L,inte){//插入
intm=0,i=0;
int*p=&L.elem[0],*j=&L.elem[0];
if(L.length==0)
{*p=e;L.length++;return1;}
for(i;i<L.length;i++)
if(e>=*(p+i))
m=i+1;
for(i=L.length;i>m;i--)
*(j+i)=*(j+i-1);
L.elem[m]=e;
L.length++;
return1;
}
voidPrint(Sqlist&L,intn){//
遍历
打印输出
intk=1,i=0;int*p=&L.elem[0];
for(i=0;i<n*n;i++,k++){
printf("%d",*(p+i));
if(k==n){k=0;printf(" ");}}
printf(" ");
}
intReturnK(Sqlist&L,intk){//返回第K个元素的值
int*p=&L.elem[0];
return*(p+k-1);
}
voidFuK(Sqlist&L,intk,inte){//将第k个元素赋值为e
int*p=&L.elem[0];
*(p+k-1)=e;
}
intTiaoJian(SqlistL,intn,int&e){//是否满足皇后问题判断
intb[100];
intm=0,h=2*n;
for(intk=0;k<2*n;k++)b[k]=0;
for(inti=1;i<=n*n;i++)
if(ReturnK(L,i)==1)
{b[m]=(i-1)/n+1;m++;b[m]=i-(b[m-1]-1)*n;m++;}
for(intc=0;c<2*n;c++)
if(b[c]==0){h=c;break;}
for(c=0;c<h-2;c=c+2)
for(intd=c+2;d<h;d=d+2)
if(b[c]==b[d]||b[c+1]==b[d+1]||b[d+1]-b[c+1]==b[d]-b[c]||b[d+1]-b[c+1]==b[c]-b[d])
return0;
if(h==2*n){
printf(" %d皇后问题第%d个排列！ ",n,e);e++;
}
return1;
}
voidTrial(Sqlist&L,inti,intn,int&e){//皇后问题
intj;
if(i>n){Print(L,n);}
elsefor(j=1;j<=n;j++){
FuK(L,n*i-n+j,1);
if(TiaoJian(L,n,e)==1)
Trial(L,i+1,n,e);
FuK(L,n*i-n+j,0);
}
}
voidmain(){
intk,i=0;
printf(" 请输入要n皇后问题个数： ");
scanf("%d",&k);
time_trawtime;
structtm
*timeinfo;
time(&rawtime);
timeinfo=localtime(&rawtime);
SqlistL1;
InitList(L1);
for(i=0;i<k*k;i++)
Insert(L1,0);
inte=1;
Trial(L1,1,k,e);
printf("Thecurrentdate/timeis:%s",asctime(timeinfo));
time(&rawtime);
timeinfo=localtime(&rawtime);
printf("Thecurrentdate/timeis:%s",asctime(timeinfo));
printf("哈哈哈哈(^o^)/~ ");
system("pause");
}
Ⅷ 用回溯法解定和子集问题、0/1背包问题和n皇后问题的算法比较
我只写了一个n皇后的解法，其它的没写，不知道什么意思。程序如下：
#include <iostream>
using namespace std;
#define MAX 5 //数组维数
static int total=0; //算法总数
int array[MAX][MAX]; //定义数组
void SetArray() //数组置零
{
int i,j;
for(i=0;i<MAX;i++)
for(j=0;j<MAX;j++)
array[i][j]=0;
}
bool IsTrue(int a,int b) //合法性判断
{
int i,j,len;
for (i=0;i<MAX;i++)
if(array[a][i]==1||array[i][b]==1)
return false;
len=(a<b?a:b);
for(i=a-len,j=b-len;i<MAX&&j<MAX;i++,j++)
if(array[i][j]==1)
return false;
for(i=a,j=b;i<MAX&&j>=0;i++,j--)
if(array[i][j]==1)
return false;
for(i=a,j=b;i>=0&&j<MAX;i--,j++)
if(array[i][j]==1)
return false;
return true;
}
void show() //显示结果
{
int i,j;
cout<<"第"<<++total<<"种结果为："<<endl;
for (i=0;i<MAX;i++)
{
for(j=0;j<MAX;j++)
cout<<array[i][j]<<" ";
cout<<endl;
}
}
bool Queen(int i) //皇后算法
{
int j;
for(j=0;j<MAX;j++)
{
if(IsTrue(i,j))
{
array[i][j]=1;
if(i==MAX-1)
{
show();
array[i][j]=0;
continue;
}
else if(!Queen(i+1))
{
array[i][j]=0;
continue;
}
}
}
return false;
}
void main()
{
int i;
for(i=0;i<MAX;i++)
{
SetArray();
array[0][i]=1;
Queen(1);
}
}
不明白的可以来问我。。
Ⅸ 求n皇后问题的各种算法
n皇后的算法只有DFS
优化倒是有几个，1.位运算优化,2.旋转对称优化,建议你网络一下 USACO 跳棋的挑战,就是n皇后问题，这是经典题
Ⅹ n皇后问题
输出结果没有做什么处理
直接打印的
以前写过打印图形的，懒得搞了
#include <iostream.h>
#include <math.h>
bool Place(int x[],int k) //考察皇后k放置在x[k]列是否发生冲突
{ int i;
for (i=1; i<k; i++)
if (x[k]==x[i]||abs(k-i)==abs(x[k]-x[i]))
return 0;
return 1;
}
void Output(int n,int x[])
{
cout<<"[";
for(int i=1;i<n;i++)
cout<<x[i]<<",";
cout<<x[n]<<"]"<<endl;
return;
}
void Queue(int n,int x[])
{
int i;
for (i=1;i<=n;i++) //初始化
x[i]=0;
int k=1;
int num=0;
while(k>=1)
{
x[k]=x[k]+1; //在下一列放置第k个皇后
while (x[k]<=n && !Place(x,k))
x[k]=x[k]+1; //搜索下一列
if (x[k]<=n && k==n) { //得到一个解，输出
Output(n,x);
num++;
}
else if (x[k]<=n && k<n)
k=k+1; //放置下一个皇后
else {
x[k]=0; //重置x[k]，回溯
k=k-1;
}
}
}
int main(int argc, char *argv[])
{
cout<<"请输入皇后的个数\n";
int n;
cin>>n;
int *x=new int[n];
x[0]=0;
Queue(n,x);
return 0;
}