n皇後問題分支限界演算法

A. c語言 N皇後問題

q[j] == i表示與上個棋子同列（同行是不可能，不用考慮），還有情況得舍棄的就是斜線，左斜和右斜，)(abs(q[j]-i)==(abs(j-k))))這個就表示與前面的棋子是否在同一斜線，左斜右斜都包括了，你自己寫寫就能總結出這個式子了，數學計算而已。不懂HI我

B. N皇後問題,提交queen.pas

n皇後問題（非遞歸）
top := 1; // 從第一個皇後開始嘗試
while (top > 0) do // 當還有活動節點時循環
if (top > n) then // 是否n個皇後都放置在棋盤了
begin
inc(count); // 找到一組解，總數加一
dec(top); // 回到上一皇後繼續
end
else // n個皇後還沒有都放置好
begin
inc(x[top]); // 當前皇後到下一列
if (x[top] > n) then // 是否超出棋盤
dec(top) // 超出棋盤，回到上一個皇後繼續
else // 沒有超出棋盤
if check(top) then // 檢查當前位置是否可以放皇後
begin
inc(top); // 可以放置，繼續嘗試下一個皇後
x[top] := 0; // 下一個皇後從第一列開始嘗試
end;
end;
n皇後問題（邊界判定）
function check(pos: integer): boolean;
var
i: integer;
begin
check := true;
for i := 1 to pos - 1 do
if (x[pos] = x[i]) or (abs(x[pos] - x[i]) = abs(pos - i)) then
begin
check := false;
break;
end;
end;
n皇後問題（遞歸）
procere search(k: integer);
var
i: integer;
begin
if k > n then // 是否前n個皇後都已經放下
inc(count)
else // 還有皇後沒放
for i := 1 to n do // 從第1列開始逐列嘗試
begin
x[k] := i; // 把第k個皇後放在第i列
if check(k) then // 第k個皇後是否可以放在第i列
search(k + 1); // 可以放，繼續處理第k+1個皇後
end;
end;

C. 誰有n皇後問題的答案

八皇後問題程序及註解
http://www.mydrs.org 2003-12-3 大榕樹

大家一定見過這種辦法吧 ,但是做為初學者理解起來特別困難 ,我就把我當時對它的理解簡單說一下,不對的地方大家給個 建議!
program eightqueens;
var
x:array[1..8] of integer;
a,b,c:array[-7..16] of boolean;
i:integer;
procere print;
var k:integer;
begin
for k:=1 to 8 do write(x[k]:4);
writeln;
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to 8 do
if a[j] and b[i+j] and c[i-j]
then begin
x:=j;
a[j]:=false;
b[i+j]:=false;
c[i-j]:=false;
if i<8 then try(i+1)
else print;
a[j]:=true;
b[i+j]:=true;
c[i-j]:=true
end
end;
begin
for i:=-7 to 16 do
begin
a:=true;
b:=true;
c:=true
end;
try(1);
end. 現在循環從 i=1 ,j:=1 to 8 do 開始 此時 計算機檢測到 i=1 j=1 簡化為(1,1)為空,佔用該位置並令該位置對應的斜線和水平方向的位置為 false ,然後程序就開始去執行try(2),注意此時計算機在i=1 這層僅僅走拉一個循環(j=1)就跳到拉i=2 這層里此時計算機從j:=1 to 8 do 又開始循環,排除 j=1,j=2 得到 (2,3)注意計算機在層里也只是走拉3(j=3)個循環然後又跳到拉i=3 這層依次類推得到(3,5),(4,2)(5,4)而在i=6 這層里計算機從j:= 1 to 8 do 都沒有找到合適的位置,此時注意在i=6 這層里計算機計算機將返回到i=5 這層里,(因為用拉遞歸)並且釋放(5,4)該位置,為什麼要釋放呢?因為原因很簡單如果不釋放的話 該位置對應的斜線和水平方向會對以後的幾層造成影響,讓計算機誤認為為false.此時的在i=5這層里 j=4才是結束,然後計算機又會從j=5到 8 開始去找合適的位置 ,如果找不到又會返回到上一層依次類推直到計算機找到一組解 輸出,假設在(8,3)這個位置是計算機找到的一組解,此時計算機又會從j=4到8 開始循環,如果找不到 計算機就會返回上一層的即i=7這層接著上一次的跳出位置走完以後的循環,依次類推不斷的返回,跳出, 求解,(即令前幾個位置不變,從第8個位置變換,沒有空位置的.接會返回上一層)最後返回到i=1這層里,注意此時在這層里也只是走拉j=1個循環然後計算機就又開始從j= 2 去試著找....大家有沒有算過求出所有的解要走過多少個循環?我想估計也不下1000個吧.其實整個過程就是一個重復的過程(即遞歸)倒著想在i=7 這層里的j=1 位置即(7,1) 計算機會去試從(8,1)到(8,8)這8 個位置,而在(7,2)也同樣會去試這8 個位置 等等在(6,1)會試(7,1)到(7,8) 等. 這是正著考慮(1,1)這里計算機會試著從(2,1)到(2,8)這8個位置而在這8 個位置里並沒有試完就有空位置 (2,3)此時計算機會在這個位置對下一層里開始試(3,1)..(3,8)依次類推,試不通的返回,接著走完上一層直到試完所有的位置!

D. N皇後問題 C++

#include<iostream>

#include<cstdio>

using namespace std;

int q[1000],s=0,n;

bool a[1000]={0},b[1000]={0},c[1000]={0};

void search(int i){

int j;

for(j=1;j<=n;j++){

if((!a[j])&&(!b[i+j])&&(!c[i-j+n-1])){

q[i]=j;

a[j]=1;

b[i+j]=1;

c[i-j+n-1]=1;

if(i==n)s++;

if(i!=n)search(i+1);

a[j]=0;

b[i+j]=0;

c[i-j+n-1]=0;}}}

int main(){

cin>>n;

search(1);

cout<<s;}

E. n皇後問題 c++

回溯法程序：
#include<iostream.h>
#include<string.h>
#include<time.h>
#define size 100
int board[size];
int ver[size];
int ru[size*2];//右上
int rd[size*2];//右下
int n,find; int rec[size];
//回溯搜索
void dfs(int t)
{
int i;
if(find) return;
if(t==n)
{
find=1;
for(i=0;i<n;i++)
{
rec[i]=board[i];
}
return;
}
for(i=0;i<n;i++)
{
if(ver[i]==1) continue;
if(ru[i-t+n]==1) continue;
if(rd[i+t]==1) continue;
ver[i]=1;
ru[i-t+n]=1;
rd[i+t]=1;
board[t]=i;
dfs(t+1);
rd[i+t]=0;
ru[i-t+n]=0;
ver[i]=0;
}
return;
}
int main()
{
int i,j,t1,t2;
cout<<"輸入棋盤大小：";
cin>>n;
t1=clock();
find=0; memset(ver,0,sizeof(ver));
memset(ru,0,sizeof(ru)); memset(rd,0,sizeof(rd));
dfs(0);
t2=clock();
if(find)
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(rec[i]==j) cout<<'X';
else cout<<'+';
}
cout<<endl;
}
else
cout<<"Can't find!n";
cout<<"耗費時間："<<t2-t1<<"msn";
return 0;
}

既然是回溯法，樓主可以看看回溯法
---------2 回溯法：如果在第i行無論如何放置皇後，都和前面i-1行的皇後互相攻擊的話，說明i-1行的皇後位置不合理，於是就回退一行，重新計算。這類似於走迷宮，如果在某個路口實在不下去了，只好退後一步重新選擇。在退後一步重新選擇的時候，顯然可以排除已經嘗過的路線。

下面重點分析回溯法解決N皇後問題。

很容易想到，在同一行上只能放置一個皇後，因此nxn的棋盤上放n個皇後的方案必然是每一行上放一個皇後。這樣的話，我們可以使用一個一維數組q[n]來保存最後的方案，其中q[i]的含義是第i行上皇後的位置。比如q[3]=5，則表示第三行上的皇後在第5格。

上面無論哪種方法，都要解決一個問題：如何量化的判斷兩個皇後是否相互攻擊？有了數組q的定義，我們很容易發現如下的規律：

對於兩個皇後q[i]和q[j]，互相不攻擊的條件是：
1 i != j，即不在同一行。
2 q[i] != q[j]，即不再同一列。
3 |q[i] - q[j]| != |i - j|，即不在一個對角線上。

根據前面的分析，我們假設前面的i-1行的皇後已經布好，即互不攻擊，則在第i行上的皇後位置為q[i]，那麼我們可以把q[i]依次和前面的i-1行比較，如果q[i]和前面的i-1行互不攻擊的話，則說明第i行的皇後q[i]就是一個合理的位置，則繼續尋找i+1行的皇後合理位置。如果第i行的皇後和前面的i-1行的某個皇後有攻擊，則第i行的皇後需要右移一格，重新和前面的i-1行進行比較。

在進行具體處理時，要注意邊界條件，即回退到棋盤第一行以及皇後已經右移到棋盤的最後一行的最後一格的情況，都意味著當前皇後位置使得N皇後問題無解。

下面是演算法：

PROCEDURE QUEEN(n)
FOR i = 1 TO n DO q[i] = 1
i = 1
loop:
IF(q[i] <= n) THEN
{
k = 1
WHILE((k < i) and ((q[k] - q[i])) * (|q[k] - q[i]| - |k - i| ) != 0)
DO k = k + 1

IF(k < i) THEN q[i] = q[i] + 1
ELSE
{
i = i + 1
IF(i > n) THEN
{
OUTPUT q[i] (i = 1,2,...,n)
q[n] = q[n] + 1
i = n
}
}
}
ELSE
{
q[i] = 1
i = i - 1
IF(i < 1) THEN RETURN
q[i] = q[i] + 1
}

TOGO loop
RETURN

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

G. 急求！！pascal n皇後問題 (遞歸） 帶詳細解析

〖問題描述〗
在一個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
if(b[j]=0)and(c[i+j]=0)and(d[i-j]=0)then
begin
a:=j;
b[j]:=1;
c[i+j]:=1;
d[i-j]:=1;
ifi<8thentry(i+1)
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);
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
(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.
方案一（深度優先搜索）：
var ans:array[1..8] of integer; //記錄答案的數組，記錄在第1到第8行皇後所在的列；
lie:array[1..8] of boolean; //記錄1到8中某列是否已經被另一個皇後佔用；
zx:array[2..16] of boolean; //正斜線（左下向右上）數組，該斜線特點為：斜線上每一格的行加列的和一定，和為從2到16. 9士捎?到16來表示這15條正斜線，於是該數組記錄了2到16中某條正斜線是否已經被另一個皇後佔用；
fx:array[-7..7] of boolean; //反斜線（左上向右下）數組，該斜線特點為：斜線上每一格的行減列的差一定，差為從-7到7 9士捎?7到7來表示這15條正斜線，於是該數組記錄了2到16中某條正斜線是否已經被另一個皇後佔用；
temp:integer; //記錄總方案數；
procere print; //該子程序負責輸出方案；
var i:integer;
begin
write('zuobiao');
for i:=1 to 8 do
write(' (',i,',',ans[i],')'); //i代錶行，ans[i]代表列；
writeln;
end;
procere search(i:integer); //i為行，即表示放到了第幾個皇後（因為一行有且只有1個皇後);
var j:integer;
begin
if i=9 then //遞歸出口，當搜索到第九行時，便得到一種方案；
begin
print; //輸出該方案；
inc(temp); //每輸出（得到）一種方案，總方案數變加1；
exit; //退出；
end;
for j:=1 to 8 do if not lie[j] and not zx[i+j] and not fx[i-j] then //當前位置，該列，正斜線，反斜線上均未被另一個皇後佔用，即可以擺放一個皇後；
begin
lie[j]:=true; //設置標志，該行
zx[i+j]:=true; // 該正斜線
fx[i-j]:=true; // 該反斜線上已被皇後佔用，不可再放皇後；
ans[i]:=j; //記錄答案（第i行皇後所在列j）；
search(i+1); //實行下一層遞歸；
lie[j]:=false; //恢復標志（回溯）；
zx[i+j]:=false;
fx[i-j]:=false;
end;
end;
begin //主程序；
temp:=0; //給總方案數設初值為0;
fillchar(lie,sizeof(lie),0); //分別給列;
fillchar(zx,sizeof(zx),0); // 正斜線;
fillchar(fx,sizeof(fx),0); // 反斜線數組設初值為False;
search(1); //從第一行開始進行搜索；
writeln(temp); //再輸出總方案數；
end.
方案二（位運算加速）：
var
upperlim,sum:integer;
procere test(row,ld,rd:integer);
var
pos,p:integer;
begin
if row<>upperlim then
begin
pos:=upperlim and not (row or ld or rd);
while pos<>0 do
begin
p:=pos and -pos;
pos:=pos-p;
test(row+p,(ld+p)shl 1,(rd+p)shr 1);
end;
end
else
inc(sum);
end;
begin
upperlim:=(1 shl 8)-1;
test(0,0,0);
writeln(sum);
end.
設置一個三維數組，第一個下標是皇後的行坐標，第二個下標是皇後的列坐標，第三個下標是殘卷號。相當於有N張疊在一起的8*8棋盤，每張棋盤只在復制前面棋盤及皇後後加放置一個皇後。直到放滿8皇後後才是一張完整的8皇後圖，稱完卷。

H. c語言常用演算法有哪些

0） 窮舉法
窮舉法簡單粗暴，沒有什麼問題是搞不定的，只要你肯花時間。同時對於小數據量，窮舉法就是最優秀的演算法。就像太祖長拳，簡單，人人都能會，能解決問題，但是與真正的高手過招，就頹了。
1） 貪婪演算法
貪婪演算法可以獲取到問題的局部最優解，不一定能獲取到全局最優解，同時獲取最優解的好壞要看貪婪策略的選擇。特點就是簡單，能獲取到局部最優解。就像打狗棍法，同一套棍法，洪七公和魯有腳的水平就差太多了，因此同樣是貪婪演算法，不同的貪婪策略會導致得到差異非常大的結果。
2） 動態規劃演算法
當最優化問題具有重復子問題和最優子結構的時候，就是動態規劃出場的時候了。動態規劃演算法的核心就是提供了一個memory來緩存重復子問題的結果，避免了遞歸的過程中的大量的重復計算。動態規劃演算法的難點在於怎麼將問題轉化為能夠利用動態規劃演算法來解決。當重復子問題的數目比較小時，動態規劃的效果也會很差。如果問題存在大量的重復子問題的話，那麼動態規劃對於效率的提高是非常恐怖的。就像斗轉星移武功，對手強它也會比較強，對手若，他也會比較弱。
3）分治演算法
分治演算法的邏輯更簡單了，就是一個詞，分而治之。分治演算法就是把一個大的問題分為若干個子問題，然後在子問題繼續向下分，一直到base cases，通過base cases的解決，一步步向上，最終解決最初的大問題。分治演算法是遞歸的典型應用。
4） 回溯演算法
回溯演算法是深度優先策略的典型應用，回溯演算法就是沿著一條路向下走，如果此路不同了，則回溯到上一個
分岔路，在選一條路走，一直這樣遞歸下去，直到遍歷萬所有的路徑。八皇後問題是回溯演算法的一個經典問題，還有一個經典的應用場景就是迷宮問題。
5） 分支限界演算法
回溯演算法是深度優先，那麼分支限界法就是廣度優先的一個經典的例子。回溯法一般來說是遍歷整個解空間，獲取問題的所有解，而分支限界法則是獲取一個解（一般來說要獲取最優解）。

I. pascal跳馬問題的思路

用回溯和遞歸結合
有個例子參考

n皇後問題的遞歸演算法如下：

program hh;
const n=8;
var i,j,k:integer;
x:array[1..n] of integer;
function place(k:integer):boolean;
var i:integer;
begin
place:=true;
for i:=1 to k-1 do
if (x[i]=x[k]) or (abs(x[i]-x[k])=abs(i-k)) then
place:=false ;
end;
procere print;
var i:integer;
begin
for i:=1 to n do write(x[i]:4);
writeln;
end;
procere try(k:integer);
var i:integer;
begin
if k=n+1 then begin print; exit end;
for i:= 1 to n do
begin
x[k]:=i;
if place(k) then try(k+1);
end;
end ;
begin
try(1);
end.

程序2：

說明:當n=8 時有30條對角線分別用了l和r數組控制，

用c數組控制列.當(i,j)點放好皇後後相應的對角線和列都為false.遞歸程序如下:

program nhh;
const n=8;
var s,i:integer;
a:array[1..n] of byte;
c:array[1..n] of boolean;
l:array[1-n..n-1] of boolean;
r:array[2..2*n] of boolean;
procere output;
var i:integer;
begin
for i:=1 to n do write(a[i]:4);
inc(s);writeln(' total=',s);
end;
procere try(i:integer);
var j:integer;
begin
for j:=1 to n do
begin
if c[j] and l[i-j] and r[i+j] then
begin
a[i]:=j;c[j]:=false;l[i-j]:=false; r[i+j]:=false;
if i<n then try(i+1) else output;
c[j]:=true;l[i-j]:=true;r[i+j]:=true;
end;
end;
end;
begin
for i:=1 to n do c[i]:=true;
for i:=1-n to n-1 do l[i]:=true;
for i:=2 to 2*n do r[i]:=true;
s:=0;try(1);
writeln;
end.