C语言|C语言算法,八皇后问题,回溯算法

问题:八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以解决此问题。
此代码1适合初学接触,找到了八皇后的一种
#include


void PrintEight(int q[]){
int i, j;
for (i = 0; i<8; i++){
printf("\n");
for (j = 0; j<8; j++){
if (j == q[i])
printf(" 十");
else
printf(" 口");
}
}
}


int main(void){
int top = -1, j = 0, i;
int q[8];
int left[15] ={0},right[15] ={0},cal[8] = { 0 };


for (i = 0; i < 8; ){
for (; j < 8; j++){
if (!cal[j] && !left[7 - j + i] && !right[i + j]){
q[++top] = j;
cal[j] = left[7 - j + i] = right[i + j] = 1;
i++;
j = 0;
break;
}
}
if (j == 8){
i--;
top--;
j = q[i] + 1;
cal[q[i]] = left[7 - j + i + 1] = right[i + j - 1] = 0;
}
}
PrintEight(q);
printf("\n");


return 0;
}



此代码2是利用非递归找到八皇后的所有解
#include


int cal[8]={0};
int left[15]={0};
int right[15]={0};
int Q[8];
int top=-1;
int cnt=0;


void PrintQueen()
{
int i,j;
printf("第%d组解为:\n",++cnt);
for(i=top; i>-1; i--){
for(j=0; j<8; j++){
if(Q[i]==j)printf("Q");
else printf("X");
}
printf("\n");
}
}


void EightQueen()
{
int j=0;
for(int i=0; i<8; ){
for(; j<8; j++){
if(!cal[j]&&!left[j+i]&&!right[7-j+i]){
break;
}
}
if(j<8){
Q[++top]=j;
cal[j]=left[i+j]=right[7-j+i]=1;
if(i<7){
i++; j=0;
}
else {
PrintQueen();
i=top; j=Q[top--];
cal[j]=left[i+j]=right[7-j+i]=0;
j++;
}
}
else {
i=top; j=Q[top--];
cal[j]=left[i+j]=right[7-j+i]=0;
j++;
}
/*条件整合后
if(j<8){
Q[++top]=j;
cal[j]=left[i+j]=right[7-j+i]=1;
if(i<7){
i++; j=0;
}
else PrintQueen();
}
if(j==8){
i=top; j=Q[top--];
cal[j]=left[i+j]=right[7-j+i]=0;
j++;
}
*/
if(i==-1) break;
}
}
int main (void)
{
EightQueen();
return 0;
}



此代码3是利用递归找到八皇后的所有解,也是相对公认好一点的方法




#include


int cal[8]={0};
int left[15]={0};
int right[15]={0};
int Q[8];
int cnt=0;


void PrintQueen()
{
int i,j;
printf("第%d组解为:\n",++cnt);
for(i=0; i<8; i++){
for(j=0; j<8; j++){
if(Q[i]==j)printf("Q");
else printf("X");
}
printf("\n");
}
}


void EightQueen(int i)
{
for(int j=0; j<8; j++){
if(!cal[j]&&!left[j+i]&&!right[7-j+i]){
Q[i]=j;
cal[j]=left[j+i]=right[7-j+i]=1;
if(i<7) EightQueen(i+1);
else PrintQueen();
//
cal[j]=left[j+i]=right[7-j+i]=0;
/*该句一定要放在if里面,不可放在if外面。
因为if条件不成立就不会执行,该语句也不会执行,只有当递归返回、输出棋盘后才会执行。
若放在if之外,那么if不成立就会执行,且随着j++,进行“抹皇后”操作
*/
}
}
}
int main (void)
{
EightQueen(0);
return 0;
}

【C语言|C语言算法,八皇后问题,回溯算法】



    推荐阅读