python八皇后函数 八皇后问题python回溯

数据结构 八皇后

去图书馆找找有关 数据结构 或是 算法设计 的书，一般都有8皇后的源代码

站在用户的角度思考问题，与客户深入沟通，找到翁牛特网站设计与翁牛特网站推广的解决方案，凭借多年的经验，让设计与互联网技术结合，创造个性化、用户体验好的作品，建站类型包括：网站设计、做网站、企业官网、英文网站、手机端网站、网站推广、主机域名、虚拟主机、企业邮箱。业务覆盖翁牛特地区。

8皇后算法是算法的经典了 我记得我当年C语言程序上机就有这道题目 我直接按书上抄上去的 找不到的话就去网上下 网上下的一般会有很多错误 但一般是小错误 反复改下错就可以了

数据结构递归八皇后问题，如下代码，自己认为思想没错，为何得不到正确结果

代码没发全不好帮你看。思路懂了应该没大问题。但你这样写太复杂了。搞三个数组记一下每个点是否被行列斜覆盖了就可以了。

#includeiostream

#includecstdlib

using namespace std;

int a[21],b[21],c[21],p[21][21],ans;

void pr(){

cout++ansendl;

int i,j;

for(i=1;i=8;i++){

for(j=1;j=8;j++)coutp[i][j]" ";

coutendl;

}

}

void dfs(int k){

int i;

if(k==9){pr();return;}

for(i=1;i=8;i++)if((!a[i])(!b[i+k])(!c[k-i+7])){

a[i]=b[i+k]=c[k-i+7]=1;p[k][i]=1;

dfs(k+1);

a[i]=b[i+k]=c[k-i+7]=0;p[k][i]=0;

}

}

int main(){

dfs(1);

system("pause");

return 0;

}

八皇后问题的解决方法

八皇后问题的精典c 源代码

#include graphics.h

#include stdlib.h

#include stdio.h

#include dos.h

char n[3]={\'0\',\'0\'};/*用于记录第几组解*/

int a[8],b[15],c[24],i;

int h[8]={127,177,227,277,327,377,427,477};/*每个皇后的行坐标*/

int l[8]={252,217,182,147,112,77,42,7};/*每个皇后的列坐标*/

void *arrow;

void try(int i)

{int j;

for (j=1;j=8;j++)

if (a[j-1]+b[i+j-2]+c[i-j+7]==3) /*如果第i列第j行为空*/

{a[j-1]=0;b[i+j-2]=0;c[i-j+7]=0;/*占用第i列第j行*/

putimage(h[i-1],l[j-1],arrow,COPY_PUT);/*显示皇后图形*/

delay(500);/*延时*/

if(i8) try(i+1);

else /*输出一组解*/

{n[1]++;if (n[1]\'9\') {n[0]++;n[1]=\'0\';}

bar(260,300,390,340);/*显示第n组解*/

outtextxy(275,300,n);

delay(3000);

getch();

}

a[j-1]=1;b[i+j-2]=1;c[i-j+7]=1;

putimage(h[i-1],l[j-1],arrow,XOR_PUT);/*消去皇后，继续寻找下一组解*/

delay(500);

}

}

int main(void)

{int gdrive=DETECT,gmode,errorcode;

unsigned int size;

initgraph(gdrive,gmode,"c:\\\\tc\\\\bgi");

errorcode=graphresult();

if (errorcode!=grOk)

{printf("Graphics error\\n");exit(1);}

rectangle(50,5,100,40);

rectangle(60,25,90,33);

/*画皇冠*/

line(60,28,90,28);line(60,25,55,15);

line(55,15,68,25);line(68,25,68,10);

line(68,10,75,25);line(75,25,82,10);

line(82,10,82,25);line(82,25,95,15);

line(95,15,90,25);

size=imagesize(52,7,98,38); arrow=malloc(size);

getimage(52,7,98,38,arrow);/*把皇冠保存到缓冲区*/

clearviewport();

settextstyle(TRIPLEX_FONT, HORIZ_DIR, 4);

setusercharsize(3, 1, 1, 1);

setfillstyle(1,4);

for (i=0;i=7;i++) a[i]=1;

for (i=0;i=14;i++) b[i]=1;

for (i=0;i=23;i++) c[i]=1;

for (i=0;i=8;i++) line(125,i*35+5,525,i*35+5);/*画棋盘*/

for (i=0;i=8;i++) line(125+i*50,5,125+i*50,285);

try(1);/*调用递归函数*/

delay(3000);

closegraph();

free(arrow);

}

寻求八皇后的迭代算法解释。

也不知是不是你想要的解释，采用回溯法：（以前写的，直接粘贴……）

用一个函数来判断某个位置是否安全，安全的位置说明它所在的行、列和对角线上都没有放置皇后，因此不会出现皇后互相攻击的情况；否则该位置不安全。其具体实现的过程是找出所有放置过的皇后，将它们的位置与该位置进行比较判断。又注意到同一行最多只能放置一个皇后，因此，只需要对前面的各行逐行扫描皇后，就可以找出所有皇后的位置。

为便于显示，假设棋盘的状态为“-”时表示未放皇后状态，为“Q”时表示放置了皇后的状态。

//

判断位置(

row,

col

)是否是安全位置

bool

safeJudge(

int

row,

int

col

)

const

{

int

qRow,

qCol;

//

检查前面各行，看与前面放置的皇后是否发生攻击

for(

qRow

=

0;

qRow

row;

qRow++

)

{

string

rowState

=

chessState[

qRow

];

//

寻找第qRow行放置皇后的列数

qCol

=

rowState.find(

"Q"

);

//

判断是否安全

if(

qRow

==

row

||

qCol

==

col

||

(

qCol

-

qRow

)

==

(

col

-

row

)

||

(

qCol

+

qRow

)

==

(

col

+

row

)

)

return

false;

}

return

true;

}

试着先把第一个皇后放在棋盘上，然后再放第二个皇后，使两个皇后不会互相攻击，再放第三个皇后，使得它与前两个皇后都不会互相攻击，以此类推，直至所有的皇后都放上去。如果第七个皇后放上后，第八个皇后已经没有安全位置可以放置，则试着调整第七个皇后的位置，再尝试第八个皇后有没有安全位置；如果第七个皇后的所有安全位置都已尝试过了，第八个皇后还是没有安全位置，则试着调整第六个皇后的位置。如此类推，最糟糕的情况是一直到将第一个皇后的位置进行调整。由此可见，采用回溯法，过程的实现形式非常简单自然，然而这一过程的工作量非常大。

void

QueenChess::placeQueen(

int

row

)

{

//

穷尽第row行的所有列

for(

int

col

=

0;

col

8;

col++

)

{

if(

safeJudge(

row,

col

)

)

{

chessState[

row

][

col

]

=

"Q";

//

若还没有放到第八行，则尝试下一行

if(

row

7

)

placeQueen(

row

+

1

);

//

已经放置了八个皇后，打印出成功的棋盘，并将解数加1

else

{

solves++;

drawChess();

}

}

//

将该处的皇后取走，尝试下一列位置

chessState[

row

]

=

"--------";

}

}

这个算法能发现所有可能的解，不过它认为棋盘是具有行列编号的。事实上，棋盘并没有行列编号，如位置（0,0）和（7,7）其实是对称位置，因此这种算法给出的某些解也是对称的。为了便于理解，假设棋盘是具有行列编号的。

建立一个QueenChess类，见相应程序。

QueenChess::QueenChess()

{

solves

=

0;

for(

int

i

=

0;

i

8;

i++

)

chessState[

i

]

=

"--------";

}

void

QueenChess::drawChess()

{

int

i,

j;

cout

"\n八皇后问题的第"

solves

"个解为："

endl;

cout

"

1

2

3

4

5

6

7"

endl;

for(

i

=

0;

i

8;

i++

)

{

cout

i

"

";

for(

j

=

0;

j

8;

j++

)

cout

chessState[

i

][

j

]

"

";

cout

endl;

}

system(

"pause"

);

}

void

QueenChess::solve()

{

//

从第0行开始放置皇后

placeQueen(

);

cout

"\n八皇后问题总共的解的个数为："

solves

endl;

}

一行Python 能实现什么丧心病狂的功能

1行python解八皇后，其中一大半代码是用于打印出来带格式的。_=[__import__('sys').stdout.write("\n".join('.' * i + 'Q' + '.' * (8-i-1) for i in vec) + "\n===\n") for vec in __import__('itertools').permutations(xrange(8)) if 8 == len(set(vec[i]+i for i in xrange(8))) == len(set(vec[i]-i for i in xrange(8)))]

什么是 八皇后问题

作者：est

链接：

来源：知乎

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。