回溯法实验(n皇后问题)(迭代法)

算法分析与设计实验报告第

三

次附加实验

1. 2.

n

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() //迭代法实现回溯函数{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

过一定程度的思考也能写出来了，感觉还是很开心的。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++){"请输入皇后的个数："; //输入皇后个数"皇后问题的解为："clock_t

start,end,over; start=clock();end=clock();over=end-start;start=clock(); cout<<n<<"皇后问题共有";cout<<m<<"个不同的解！" 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类的对象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++){"请输入皇后的个数：";cout<<n<<"皇后问题的解为："clock_t

start,end,over; start=clock();end=clock();over=end-start;start=clock(); cout<<n<<"皇后问题共有";cout<<m<<"个不同的解!"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