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;
}