1樓：匿名使用者
〖問題描述〗
在乙個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;
procedureprint;
begin
t:=t+1;
write(t,'');
fork:=1to8dowrite(a[k],'');
writeln;
end;
proceduretry(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; //統計總數}
procedure 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;
procedure 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.
2樓：楊雨欣
programtt;
vara:array[1..8]ofinteger;
b,c,d:array[-7..16]ofinteger;
t,i,j,k:integer;
procedureprint;
begin
t:=t+1;
write(t,'');
fork:=1to8dowrite(a[k],'');
writeln;
end;
proceduretry(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.
3樓：
八皇后問題..我也正在學。演算法是回溯演算法，首先要使八個皇后不在同一行，同一列，同一對角線上（包括『\』或『/』），不妨設每乙個皇后各佔一列。
則有八列(陣列a[1..8]:boolean)表示是否安全【有沒有皇后佔了】，八行(b[1..
8]:boolean)，那麼，對角線怎麼算呢？舉個例子：
位置[5,5]和位置[8,8]，很明顯是相對的，怎麼用演算法算出來？觀察一下：5-5=0 = 8-8=0,明白了嗎？
假設位置[1,8]和位置[8,1]是相對的。怎麼用演算法算出來？觀察一下：
1+8=9 = 8+1=9,明白了嗎？測試乙個位置是否與皇后的位置對角線不相對，設已佔位皇后的位置是[ i,j ]，測試皇后的位置是[ a,b ]，兩個位置對角線不相同則必須 (i-j<>a-b) and (i+j<>a+b)。綜合起來要想測試兩個皇后是否受攻擊，則表示式是：
if (i<>a) and (j<>b) and (i-j<>a-b) and (i+j<>a+b)。程式請樓主和我一起研究..打了好多字呢，希望樓主能採納。
我編出了程式會和樓主一起**。
4樓：匿名使用者
方案一（深度優先搜尋）：
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; //記錄總方案數；
procedure print; //該子程式負責輸出方案；
var i:integer;
begin
write('zuobiao');
for i:=1 to 8 do
write(' (',i,',',ans[i],')'); //i代表行，ans[i]代表列；
writeln;
end;
procedure 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.
方案二（位運算加速）：
varupperlim,sum:integer;
procedure test(row,ld,rd:integer);
varpos,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;
endelse
inc(sum);
end;
begin
upperlim:=(1 shl 8)-1;
test(0,0,0);
writeln(sum);
end.
什麼是八皇后問題，什麼是 八皇后問題 呀
問題描述 在乙個8 8的棋盤裡放置8個皇后，要求每個皇后兩兩之間不相 衝 在每一橫列豎列斜列只有乙個皇后 問題分析 聿懷中學 呂思博 這道題可以用遞迴迴圈來做，分別一一測試每一種擺法，直到得出正確的答案。主要解決以下幾個問題 1 衝突。包括行 列 兩條對角線 1 列 規定每一列放乙個皇后，不會造成列...
八皇后問題求解方法分類，八皇后問題解決思路
看看這 講的很詳細。八皇后問題解決思路 先宣告我們根據條件可以知道皇后肯定是每行都有且只有乙個所以我們建立乙個陣列x t 讓陣列角標表示八皇后的行，用這個角標對應的陣列值來確定這個皇后在這行的那一列。我們用遞迴來做 這問題要求皇后所在的位置必須和其他皇后的位置不在同一行 列還有 把兩個皇后看成點其 ...
天龍八部刷f技巧，天龍八部刷跑怎麼增加掉F機率
人品就是運氣啊，你一天乙個f就不錯了，經常看見區里有人罵gm說一周跑跑乙個符沒出的。刷符真的沒技巧的，只能拼人品，你就天天跑滿5趟唄，這樣總會刷夠的。另外其實不建議這麼早做神器，有你刷出52級符的時間可能你已經60多級了，神器的話80，90再做比較好，那時候公升級也慢，刷符也慢，所以就平衡了。這個遊...