AI时代，找源码已成为过去式，纪念我过去的十年0(回)
2天前
还有人吗2(回)
20天前会python真的可以为所欲为0(回)
500天前
这里还有人吗2(回)
685天前这里还有人吗0(回)
685天前
每天面对着电脑屏幕，敲打键盘。我所面对的并不只是代码，而是一种生活方式。0(回)
910天前#include<stdio.h> |
#include<stdlib.h> |
#define N 8 |
/*八皇后 ： 西洋棋中的皇后可以直线前进，吃掉遇到的所有棋子，如果棋盘上有八个皇后，则这八个皇后如何相安无事的放置在棋盘上？*/ |
/*解法 ： 关于棋盘的问题，都可以用递回求解，然而如何减少递回的次数？在八个皇后的问题中,不必要所有的格子都检查过，例如若某列检查过，该该列的其它格子就不用再检查了，这个方法称为分支修剪。*/ |
int column[N+1];// 同栏是否有皇后，1表示有 |
int rup[2*N+1];// 右上至左下是否有皇后 |
int lup[2*N+1];// 左上至右下是否有皇后 |
int queen[N+1]={0}; |
int num;// 解答编号 |
void backtrack ( int );// 递回求解 |
int main ( void ) |
{ |
int i; |
num=0; |
for ( i=1; i<=N; i++ ) |
column[i]=1; |
for ( i=1; i<=2*N; i++ ) |
rup[i]=lup[i]=1; |
backtrack ( 1 ); |
return 0; |
} |
void showAnswer() |
{ |
int x,y; |
printf ( "\n解答%d\n",++num ); |
for ( y=1; y<=N; y++ ) |
{ |
for ( x=1; x<=N; x++ ) |
{ |
if ( queen[y]==x ) |
{ |
printf ( "Q" ); |
} |
else |
{ |
printf ( "." ); |
} |
} |
printf ( "\n" ); |
} |
} |
void backtrack ( int i ) |
{ |
int j; |
if ( i>N ) |
{ |
showAnswer(); |
} |
else |
{ |
for ( j=1; j<=N; j++ ) |
{ |
if ( column[j]==1&& |
rup[i+j]==1&&lup[i-j+N]==1 ) |
{ |
queen[i]=j; |
// 设定为占用 |
column[j]=rup[i+j]=lup[i-j+N]=0; |
backtrack ( i+1 ); |
column[j]=rup[i+j]=lup[i-j+N]=1; |
} |
} |
} |
} |
