Ⅰ 如何用C語言解決N皇後問題並作出流程圖
#include"iostream"
using namespace std;
const max_board = 13;
class Queen
{
public :
Queen(int size);
bool is_solved() const; //判斷是否已經填滿
void print() const; //列印結果
bool unguarded(int col) const; //判斷是否被鎖定
void insert(int col); /首旁/在該位放置皇後
void remove(int col); //移除皇後
// void solve_from(Queen &configuration);
int board_size; //邊界
private :
int count; //已放置皇後的數目
bool queen_square[max_board][max_board]; //棋盤
};
Queen::Queen(int size)
{
if(size<1)
board_size=1;
else
if(size>13)
board_size=13;
else
board_size=size;
count=0;
for(int i=0;i<board_size;i++)
for(int j=0;j<board_size;j++)
{
queen_square[i][j]=false;
}
}
bool Queen::is_solved() const
{
return count==board_size;
}
void Queen::print() const
{
for(int i=0;i<board_size;i++)
{
for(int j=0;j<board_size;j++)
{
cout<<queen_square[i][j]<<' ';
}
cout<<endl;
}
cout<<仔芹迅endl;
}
bool Queen::unguarded(int col) const
{
int i;
bool ok=true;
for(i=0;ok&&i<count;i++)
{
ok=!queen_square[i][col];
}
for(i=1;i<=col&&i<念此=count&&ok;i++)
{
ok=!queen_square[count-i][col-i];
}
for(i=1;i<board_size-col&&i<=count&&ok;i++)
{
ok=!queen_square[count-i][col+i];
}
return ok;
}
void Queen::insert(int col)
{
queen_square[count++][col]=true;
}
void Queen::remove(int col)
{
queen_square[--count][col]=false;
}
void solve_from(Queen &configuration)
{
if(configuration.is_solved())
configuration.print();
else
for(int col=0;col<configuration.board_size;col++)
if(configuration.unguarded(col))
{
configuration.insert(col);
solve_from(configuration);
configuration.remove(col);
}
}
int main()
{
int n;
cout<<"please input the size:\t";
cin>>n;
Queen queen(n);
solve_from(queen);
return 0;
}
Ⅱ N皇後問題的回溯法求解屬於子集樹還是排列樹 詳細講一講
「八皇後」問題遞歸法求解 (Pascal語言) 八皇後問題是一個古老而著名的問題，是回溯演算法的典型例題。該問猜羨哪題是十九世紀著名的數學家高斯1850年提出：在8X8格的國際象棋上擺放八個皇後，使其不能互相攻擊，即任意兩個皇後都不能處於同一行、同一列或同一斜線上，問有多少種擺法。高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發表了40種不同的解，後來有人用圖論的方法解出92種結果。穗碼現代教學中，把八皇後問題當成一個經典遞歸演算法例題。 演算法分析：數組a、b、c分別用來標記沖突，a數組代表列沖突，從a[0]~a[7]代表第0列到第7列，如果某列上已經有皇後，則為1，否則為0；數組b代表主對角線沖突，為b[i-j+7]，即從b[0]~b[14]，如果某條主對角線上已經有皇後，則為1，否則為0；數組c代表從對角線沖突，為c[i+j]，即從c[0]~c[14]，如果某條從對角線上已經有皇後，則為1，否則為派前0；另優化：第一個皇後在1~4格，最後*2，即為總解數 } program queens; var a:array [1..8] of integer; b,c,d:array [-7..16] of integer; t,i,j,k:integer; procere print; begin t:=t+1; write(t,': '); for k:=1 to 8 do write(a[k],' '); writeln; end; procere try(i:integer); var j:integer; begin for j:=1 to 8 do {每個皇後都有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; if i<8 then try(i+1) {8個皇後沒有擺完，遞歸擺放下一皇後} else print; {完成任務，列印結果} b[j]:=0; {回溯} c[i+j]:=0; d[i-j]:=0; end; end; begin fillchar(a,sizeof(a),0); {初始化數組} fillchar(b,sizeof(b),0); fillchar(c,sizeof(c),0); fillchar(d,sizeof(d),0); try(1);{從第1個皇後開始放置} end. 「八皇後」問題遞歸法求解 (C語言) ＃i nclude "stdio.h" static char Queen[8][8]; static int a[8]; static int b[15]; static int c[15]; static int iQueenNum=0; //記錄總的棋盤狀態數 void qu(int i); //參數i代錶行 int main() { int iLine,iColumn; //棋盤初始化，空格為*，放置皇後的地方為@ for(iLine=0;iLine<8;iLine++) { a[iLine]=0; //列標記初始化，表示無列沖突 for(iColumn=0;iColumn<8;iColumn++) Queen[iLine][iColumn]='*'; } //主、從對角線標記初始化，表示沒有沖突 for(iLine=0;iLine<15;iLine++) b[iLine]=c[iLine]=0; qu(0); return 0; } void qu(int i) { int iColumn; for(iColumn=0;iColumn<8;iColumn++) { if(a[iColumn]==0&&b[i-iColumn+7]==0&&c[i+iColumn]==0) //如果無沖突 { Queen[iColumn]='@'; //放皇後 a[iColumn]=1; //標記，下一次該列上不能放皇後 b[i-iColumn+7]=1; //標記，下一次該主對角線上不能放皇後 c[i+iColumn]=1; //標記，下一次該從對角線上不能放皇後 if(i<7) qu(i+1); //如果行還沒有遍歷完，進入下一行 else //否則輸出 { //輸出棋盤狀態 int iLine,iColumn; printf("第%d種狀態為：\n",++iQueenNum); for(iLine=0;iLine<8;iLine++) { for(iColumn=0;iColumn2)this.width=screen.width/2" vspace=2 border=0>; } printf("\n\n"screen.width/2)this.width=screen.width/2" vspace=2 border=0>; } //如果前次的皇後放置導致後面的放置無論如何都不能滿足要求，則回溯，重置 Queen[iColumn]='*'; a[iColumn]=0; b[i-iColumn+7]=0; c[i+iColumn]=0; } } } 八皇後的c語言解法： #include #include #include int n,k,a[20],num=0; int attack(int k){ int flag=0; int i=1; while ((i<k)&&(a[k]!=a)&&(fabs(a[k]-a)!=(k-i))) i++; if (i==k) flag=1; return flag; } void place(int k) { //printf(" %d",k); int i; if (k==n+1){ num=num+1; printf("num=%d:",num); for (i=1;i<n+1;i++) printf(" %d",a); printf("\n");} else { for (i=1;i<n+1;i++){ a[k]=i; if (attack(k)==1) place(k+1); else a[k]=0; } } } main(){ scanf("%d",&n); k=1; place(k); if (k!=n+1) printf("no solution!\n"); getch(); }
Ⅲ 急求！！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皇後圖，稱完卷。
Ⅳ 利用《數據結構》課程知識完成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");
}
Ⅳ n皇後問題的演算法
# include <stdio.h>
# include <stdlib.h>
# define MAXN 20
int n,m,good;
int col[MAXN+1],a[MAXN+1];
int b[2*MAXN+1],c[2*MAXN+1];
int main()
{int j;
char awn;
printf("槐脊喚輸入n:");scanf("%d",&n);
for(j=0;j<=n;j++)a[j]=1;
for(j=0;j<=2*n;j++)b[j]=c[j]=1;
m=1;col[1]=1;good=1;col[0]=0;
do{
if (good)
if (m==n)
{
printf("列\t\t行\n");
for (j=1;j<=n;j++) printf("%3d\t%d\n",j,col[j]);
scanf("%c",&awn);
if (awn=='鉛凱Q'||awn=='q') exit(0);
while (col[m]==n)
{
m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
else {
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
col[++m]=1;
}
else {
while (col[m]==n){
m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
}while (m!=0);
}
我看這個30+也要算一野拍陣子
Ⅵ 八皇後問題求解的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
Ⅶ 用回溯法解定和子集問題、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×n格的棋盤上放置彼此不受攻擊的n個皇後。按照國際象棋的規則，皇後可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n後問題等價於再n×n的棋盤上放置n個皇後，任何2個皇後不妨在同一行或同一列或同一斜線上。
輸入：
給定棋盤的大小n (n ≤ 13)
輸出：
輸出有多少種放置方法。
二、解題思路：
要解決N皇後問題，其實就是要解決好怎麼放置這n個皇後，每一個皇後與前面的所有皇後不能在同一行、同一列、同一對角線，在這里我們可以以行優先，就是說皇後的行號按順序遞增，只考慮第i個皇後放置在第i行的哪一列，所以在放置第i個皇後的時候，可以從第1列判斷起，如果可以放置在第1個位置，則跳到下一行放置下一個皇後。如果不能，則跳到下一列...直到最後一列，如果最後一列也不能放置，則說明此時放置方法出錯，則回到上一個皇後向之前放置的下一列重新放置。此即是回溯法的精髓所在。當第n個皇後放置成功後，即得到一個可行解，此時再回到上一個皇後重新放置尋找下一個可行解...如此後，即可找出一個n皇後問題的所有可行解。
三、復雜度分析：
關於N皇後問題的復雜度問題可以說是眾說紛紜了，自己也改變過好幾次，剛開始以為棋盤是n行n列，所以理所當然應該是n^2,後來發現在每列選擇可否放置的比較上又做了一次循環，所以應該是n^3，但想了很久，發謹者現判斷可否放置的時候不是每次都循環到n,它是根據皇後i的取值而變化的，所以復雜度應該是1/3 n^3左右，即是小於n^3的。
四、測試代碼：
在這里我寫了兩個實現方法，一個是遞歸回溯，一個是迭代回溯，思路都一樣，只是形式不同罷了。
遞歸回溯：
C代碼
#include<stdio.h>
#define N 15
int n; //皇後個數
int sum = 0; //可行解個數
int x[N]; //皇後放置的列數
int place(int k)
{
int i;
for(i=1;i<k;i++)
if(abs(k-i)==abs(x[k]-x[i]) || x[k] == x[i])
return 0;
return 1;
}
int queen(int t)
{
if(t>n && n>0) //當放置的皇後超過n時，可行解個數加1，老雀此時n必須大於0
sum++;
else
for(int i=1;i<=n;i++)
{
x[t] = i; //標明第t個皇後放在第i列
if(place(t)) //如果可以放在某一位置，則繼續放下一皇後
queen(t+1);
}
return sum;
}
int main()
{
int t;
scanf("%d",&n);
t = queen(1);
if(n == 0) //如果n=0，則可行解個數為0，這種情況一定不要忽略
t = 0;
printf("%d",t);
return 0;
}
迭代回溯：
C代碼侍晌早
#include<stdio.h>
#define N 15
int n;
int sum = 0;
int x[N];
int place(int k)
{
int i;
for(i=1;i<k;i++)
if(abs(k-i)==abs(x[k]-x[i]) || x[k] == x[i])
return 0;
return 1;
}
int queen()
{
x[1] = 0;
int t=1;
while(t>0)
{
x[t]+=1;
while(x[t]<=n && !place(t))
x[t]++;
if(x[t]<=n)
if(t == n)
sum++;
else
x[++t] = 0;
else
t--;
}
return sum;
}
int main()
{
int t;
scanf("%d",&n);
t = queen();
printf("%d",t);
return 0;
}
迭代回溯的注釋因為和遞歸回溯差不多，所以就不再附註了。在這里我們可以看到，遞歸回溯非常簡單，結構很清晰，但它有一個潛在的問題存在，即當隨著變數n的增大，遞歸法的復雜度也將成幾何級增長，也有可能會出現重復的情況，所以我們在解決問題時，如果能用迭代法解決，最好還是不要用遞歸法，除非你已經對這個遞歸了如指掌了。
通過這個N皇後問題，我想大概已經把回溯法講得很清楚了吧，回溯法得到的解展開就是一個樹，很多方法都是可以通過回溯法來解決的，效率很高，但如果基數過大的話，回溯法就顯得不是那麼適用了，這也是回溯法的弱勢吧。比如說這個N皇後問題，好像當n>60的時候，回溯法就不能完全地解決問題了，這時可以考慮用概率演算法來解決，它可以解決很大的基數，只不過結果不是很精確而已。所以我們在面對一個問題時，具體是使用什麼演算法還是要結合實際情況來考慮的，目的都是更方便、更准確地解決問題。
Ⅸ 皇後問題為什麼能同時求出多個解
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皇後問題，遞歸演算法。
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;
}