回溯法實(shí)驗(yàn)(n皇后問(wèn)題)(迭代法)

算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告第

三

次附加實(shí)驗(yàn)

1. 2.

n

n

后問(wèn)題的解。其中，x[i]表示皇后

i

i

x[i]列。由于不允許將

x[i]

n

n

i

Queen

n

n

int

t){if(t>n){sum++;/*for(int

//輸出皇后排列的解{

";}}else{//回溯探索第i行的每一列是否有元素滿足要求for(int

{x[t]=i;if(Place(t)){Backtrack(t+1);}}}}

Queen::Backtrack() //迭代法實(shí)現(xiàn)回溯函數(shù){x[1]

=

0;int

=

1;{x[k]

+=

1; ((x[k]<=n)&&!(Place(k)))

{ x[k]

+=

1; }if(x[k]<=n) {if(k

==

n) {/*for

(int

{

"; }

*/sum++;}else {x[k]=0;}}else { k--; }}}

(1)

(2)

(3)

n

n

NP

Dijkstra

Dijkstra

過(guò)一定程度的思考也能寫出來(lái)了，感覺(jué)還是很開(kāi)心的。Dijkstra

std;class

Queen{friend

int

int); private:

Place(int

k);

Backtrack(int

t); int

n; int

*x;

};int

{int

for(int

i=1;i<=1;i++){"請(qǐng)輸入皇后的個(gè)數(shù)："; //輸入皇后個(gè)數(shù)"皇后問(wèn)題的解為："clock_t

start,end,over; start=clock();end=clock();over=end-start;start=clock(); cout<<n<<"皇后問(wèn)題共有";cout<<m<<"個(gè)不同的解！" end=clock();printf(

is

,()(end-start-over)/CLK_TCK);}system("pause");return

0;}

Queen::Place(int

k){for(int

j=1;j<k;j++){if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k])){return

false;}}return

true;}

int

t){if(t>n){sum++;/*for(int

//輸出皇后排列的解{

";}}else{//回溯探索第i行的每一列是否有元素滿足要求for(int

{x[t]=i;if(Place(t)){Backtrack(t+1);}}}}int

int

n){Queen

X; //定義Queen類的對(duì)象Xint

new

int[n+1];

for(int

{p[i]=0;}X.Backtrack(1);delete[]

p;return

}

std;class

Queen{friend

int

int); private:

Place(int

k);

Backtrack(); int

n; //

int

*x; //

//

};int

{int

for(int

i=1;i<=1;i++){"請(qǐng)輸入皇后的個(gè)數(shù)：";cout<<n<<"皇后問(wèn)題的解為："clock_t

start,end,over; start=clock();end=clock();over=end-start;start=clock(); cout<<n<<"皇后問(wèn)題共有";cout<<m<<"個(gè)不同的解!"end=clock();printf(

is

,()(end-start-over)/CLK_TCK);});return

0;}

Queen::Place(int

k){for

(int

j=1;j<k;j++){if

((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))

{return

false;}}return

true;}

Queen::Backtrack() {x[1]

=

0;int

=

1;{x[k]

+=

1; ((x[k]<=n)&&!(Place(k))) {x[k]

+=

1;}if(x[k]<=n) {if(k

==

n) {/*for

(int

{

";}

*/sum++;}else {x[k]=0;}}else { k--; }}}int

in