『壹』 急求！！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皇後圖，稱完卷。
『貳』 用遞歸方法求n皇後問題（c++版本的）
#include <cstdio>
#include <cstdlib>
int n=8;
void NQueen(int k,int a[]){
int i,j;
if(k==n){
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("\n");
return;
}
for(a[k]=1;a[k]<=n;a[k]++){
for(j=0;j<k;j++)
if(a[j]==a[k]||abs(a[j]-a[k])==k-j) break;
if(j>=k)
NQueen(k+1,a);
}
}
int main()
{
int a[10];
NQueen(0,a);
return 0;
}
『叄』 C語言八皇後遞歸問題
queen[]是一個數組，其元素queen[i]表示第i個皇後位於第i行，第queen[i]（值）列。
『肆』 N皇後問題10秒內能算出的最大個數，請問什麼代碼能實現呢，這個最大的個數是多少，代碼又是什麼
packagecom.newflypig.eightqueen;
importjava.util.Date;
/**
*在8×8格的國際象棋上擺放八個皇後，使其不能互相攻擊，
*即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。
*下面使用遞歸方法解決
*@[email protected]
*
*/
publicclassEightQueen{
privatestaticfinalshortN=15; //使用常量來定義，方便之後解N皇後問題
privatestaticintcount=0; //結果計數器
privatestaticintK=0;
publicstaticvoidmain(String[]args){
for(K=9;K<=N;K++){
count=0;
Datebegin=newDate();
//初始化棋盤，全部置0
shortchess[][]=newshort[K][K];
for(inti=0;i<K;i++){
for(intj=0;j<K;j++){
chess[i][j]=0;
}
}
putQueenAtRow(chess,0);
Dateend=newDate();
System.out.println("解決"+K+"皇後問題，用時："+String.valueOf(end.getTime()-begin.getTime())+"毫秒，計算結果："+count);
}
}
(short[][]chess,introw){
/**
*遞歸終止判斷：如果row==N，則說明已經成功擺放了8個皇後
*輸出結果，終止遞歸
*/
if(row==K){
count++;
// System.out.println("第"+count+"種解：");
// for(inti=0;i<N;i++){
// for(intj=0;j<N;j++){
// System.out.print(chess[i][j]+"");
// }
// System.out.println();
// }
return;
}
short[][]chessTemp=chess.clone();
/**
*向這一行的每一個位置嘗試排放皇後
*然後檢測狀態，如果安全則繼續執行遞歸函數擺放下一行皇後
*/
for(inti=0;i<K;i++){
//擺放這一行的皇後，之前要清掉所有這一行擺放的記錄，防止污染棋盤
for(intj=0;j<K;j++)
chessTemp[row][j]=0;
chessTemp[row][i]=1;
if(isSafety(chessTemp,row,i)){
putQueenAtRow(chessTemp,row+1);
}
}
}
privatestaticbooleanisSafety(short[][]chess,introw,intcol){
//判斷中上、左上、右上是否安全
intstep=1;
while(row-step>=0){
if(chess[row-step][col]==1) //中上
returnfalse;
if(col-step>=0&&chess[row-step][col-step]==1) //左上
returnfalse;
if(col+step<K&&chess[row-step][col+step]==1) //右上
returnfalse;
step++;
}
returntrue;
}
}
『伍』 八皇後問題求解的C語言程序的實現
這是個前不久,我為別人寫的一個代碼;
八皇後問題共有92種解;
以下代碼是解決:對於固定一個皇後位置,輸出所有可能情況.
如果這不適合你的答案你可以,稍微改改的哦~~
代碼如下:
#include "stdio.h"
bool board[8][8]={0};
int num=0; //滿足條件的個數
int inix,iniy; //輸入一個皇後的初始位置
void output() //輸出
{
int i, j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
if(!board[i][j]) printf("■ ");
else printf("◆ ");
}
printf("\n");
}
num++;
printf("\n\n");
return ;
}
bool check(int x,int y) //判斷是否能放
{
int i, j ;
for(i=0; i<8 ; i++)
{
if(board[i][y]==1) return false;
}
for(i=0;i<8;i++)
{
if(board[x][i]==1) return false;
}
i=x; j=y;
while(i>0 && j>0 ) { i--; j--; }
for(;i<8 && j<8 ; i++,j++)
if(board[i][j]==1) return false;
i=x; j=y;
while(i>0 && j<7 ) {i--;j++;}
for(;i<8 && j>=0 ; i++ ,j--)
if(board[i][j]==1) return false ;
return true ;
}
void search(int x,int num) // 搜索函數
{
int i;
if(num>=8) { output(); return ;}
if(x==inix-1) search(inix,num+1);
else
{
for(i=0;i<8;i++)
{
if(check(x,i))
{
board[x][i]=1;
search(x+1,num+1);
board[x][i]=0;
}
}
}
return ;
}
int main()
{
scanf("%d %d",&inix,&iniy);
board[inix-1][iniy-1] = 1 ;
search(0,0);
printf("%d\n",num);
return 0;
}
例如:
輸入 : 1 1
輸出 :
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ◆ ■ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ■ ◆ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
◆ ■ ■ ■ ■ ■ ■ ■
■ ■ ■ ■ ■ ■ ◆ ■
■ ■ ■ ■ ◆ ■ ■ ■
■ ■ ■ ■ ■ ■ ■ ◆
■ ◆ ■ ■ ■ ■ ■ ■
■ ■ ■ ◆ ■ ■ ■ ■
■ ■ ■ ■ ■ ◆ ■ ■
■ ■ ◆ ■ ■ ■ ■ ■
4
『陸』 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;
}
『柒』 N皇後回溯問題 解釋下這程序 C語言
#include <stdio.h>
#define DelayTime 20000
#define TopX 10
#define TopY 5
int N;/*此處開始設置幾個全局變數 N即代表皇後個數*/
int a[8], b[15], c[15];
int Num = 0;/*Num代表解決方法個數*/
int row;
/******************************************************************************/
void BackTrack (int row)
{
int col;
for (col=1; col<=N; col++)
{
if (a[col-1] + b[row+col-2] + c[row-col+N-1] == 0) /*1，為什麼這里要等於0？ if語句里的3個表達式都代表什麼呢？*/
{
a[col-1] = 1;
b[row+col-2] = 1;
c[row-col+N-1] = 1;
gotoxy(col*2 + TopX, row + TopY); /* 2，這里的gotoxy（）語句是做什麼的？ 僅僅是跳到相應位置，列印Q*/
putch('Q');
if (row < N)
{
BackTrack (row + 1); /* 3，這句什麼意思? 遞歸調用*/
}
else
{
Num++;
gotoxy(40, 9); /* 4，這里又是做什麼的？什麼用？*/
printf("Num: %d ", Num);
delay(DelayTime); /* 5，這里又有什麼用？延遲*/
}
a[col-1] = 0;
b[row+col-2] = 0; /* 6，這個三個表達式怎麼又成0了？*/
c[row-col+N-1] = 0;
gotoxy(col*2 + TopX, row + TopY); /* 7，這又是什麼用?*/
putch('.');
}
}
}
/********************************************************************************/
void main()
{
int i, j;
clrscr();
gotoxy(1, 10);
printf("Input the number of queen: ");
while(N <= 0 || N > 100)
{
scanf("%d", &N);
if(N > 100) printf("Two huge number, input again:");
if(N <= 0) printf("Can's smaller than 1, again:");
}
clrscr();
for(i=1; i<=N; i++)
{
for(j=1; j<=N; j++)
{
gotoxy(i*2 + TopX, j + TopY); /* 8，這里又是什麼用? 將游標移動到指定位置說明：gotoxy（x，y）將游標移動到指定行y和列x。
*/
putch('.');
}
}
BackTrack(1); /* 9，為什麼是1呢？不是應該傳遞的是皇後的數量嗎?第一行，N為皇後的數量*/
gotoxy(12, 17); /* 10，這又是什麼用？*/
printf ("There are %d kinds of solution.\n", Num);
getch();
}
『捌』 C語言遞歸解決八皇後問題
#include<stdio.h>
intEightQueen(introw,intcol,int(*chess)[8]);
intnotdanger(introw,intcol,int(*chess)[8]);//函數聲明要放在主函數外
intsum=0;
intmain()
{
intchess[8][8],i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
chess[i][j]=0;
}
EightQueen(0,8,chess);
printf("一共有%d種方案 ",sum);
return0;
}
intEightQueen(introw,intcol,int(*chess)[8])
{
intchess2[8][8],i,j;
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{chess2[i][j]=chess[i][j];}
}
if(row==8)
{
printf("第%d種解法",sum+1);//逗號為中文輸入逗號
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
printf("%d",(*(*chess2+i)+j));//括弧不匹配
printf(" ");
}
printf(" ");
sum++;
}
else
for(j=0;j<8;j++)
{
if(notdanger(row,j,chess))
{
for(i=0;i<8;i++)
{
*(*(chess2+row)+i)=0;//raw沒有定義，你是想用row吧？
*(*(chess2+row)+j)=1;//raw沒有定義，你是想用row吧？
}
EightQueen(row+1,col,chess2);
}
}
return0;
}
intnotdanger(introw,intj,int(*chess)[8])
{
inti,k,flag1=0,flag2=0,flag3=0;
/*判斷列方向*/
for(i=0;i<8;i++)
{
if(*(*chess+i)+j)!=0)
{
flag1=1;
break;
}
}
/*判斷左上方*/
for(i=row,k=j;i>=0&&k>=0;i--,k--)//逗號為中文逗號
{
if(*(*chess+i)+k)!=0)
{
flag2=1;
break;
}
}
/*判斷右上方*/
for(i=row,k=j;i>=0&&k<8;i--,k++)//逗號為中文逗號
{
if(*(*chess2+i)+k)!=0)//括弧比匹配
{
flag3=1;
break;
}
}
if(flag1||flag2||flag3)
{
return0;
}
else
{
return1;
}
}
評註：沒有改完，你主要的地方在於中文逗號，花括弧「{}」不匹配，「（）」括弧不匹配，變數raw沒有定義，都是些低級錯誤，自己把代碼的格式調整好，然後再試試。
『玖』 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的