递归版"八皇后问题"的详细解读

源码在哪都能获取, 所以讲一下获取不到的: "八皇后问题"的详细解读 :

1. 源码 :

#include<stdio.h>

// 全局变量会自动初始化为零 :
int count = 0;

// 依据给定的棋盘和给定的位置, 判断该位置是否危险 :
int notDanger(int row, int j,int (*chess)[8])
{
int flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0;
int i, k;

// 判断该列上所有行对应的位置是否危险 :
for(i = 0; i < 8; i ++)
{
if(*(*(chess + i) + j) != 0)
{
flag1 = 1;
break;
}
}

// 判断左上方 :
for(i = row, k = j; i >= 0 && k >= 0; i--, k--)
{
if(*(*(chess + i) + k) != 0)
{
flag2 = 1;
break;
}
}

// 判断右下方 :
for(i = row, k = j; i < 8 && k < 8; i++, k++)
{
if(*(*(chess + i) + k) != 0)
{
flag3 = 1;
break;
}
}

// 判断右上方 :
for(i = row, k = j; i >= 0 && k < 8; i--, k++)
{
if(*(*(chess + i) + k) != 0)
{
flag4 = 1;
break;
}
}

// 判断左下方 :
for(i = row, k = j; i < 8 && k >= 0; i++, k--)
{
if(*(*(chess + i) + k) != 0)
{
flag5 = 1;
break;
}
}

// 危险返回 0 :
if(flag1 || flag2 || flag3 || flag4 || flag5)
{
return 0;
}
// 安全返回 1 :
else
{
return 1;
}

}
// raw: 起始行 .
// n : 列数 .
// (*chess)[8] : 8个行指针, 既列是数组, 行是指针 .
void eightQueen(int row, int n, int (*chess)[8])
{
printf("row_number: %d\n",row);
int i,j;
// 一个临时的数组 :
int chess2 [8][8];
// 将主数组复制给临时的数组 :
for(i = 0; i < 8; i ++)
{
for(j = 0; j < 8; j ++)
{
chess2[i][j] = chess[i][j];
}
}

// 等于 8 起始是第九行了, 说明已经遍历完了一个(8X8)的数组, 因为从零开始的 :
if(8 == row) // 递归的结束条件 .
{
printf("第 %d 种 :\n",count+1);
for(i = 0; i < 8; i ++)
{
for(j = 0; j < 8; j ++)
{
// -> [8] int (*a)[8] a[8][8] int *a;
printf("%d",(*(*(chess2 + i) + j)));
}
printf("\n");
}
printf("\n");
count ++;
}
else // 开始递归 .
{
// 遍历列 :
for(j = 0; j < n; j ++)
{
printf("%d %d\n",row,j);
// 判断该行中的所有列是否危险 (危险返回 0, 安全返回 1) :
if(notDanger(row, j, chess2))
{
printf("inside: %d %d\n",row,j);
for(i = 0; i < 8; i ++)
{
*(*(chess2 + row) + i) = 0;
}
// 不危险的位置赋值为 1, 其余都是 0 :
*(*(chess2 + row) + j) = 1;
// 因为一行一定只有一个安全的位置, 所以该行找到后就必须换行了 :
eightQueen(row + 1, n, chess2);
}
}
}

}

int main()
{
// 定义一个数组 :
int chess[8][8], i, j;
// 数组进行初始化 :
for(i=0;i<8;i++)
{
for(j=0;j<8;j++)
{
chess[i][j] = 0;
}
}
eightQueen(0, 8, chess);
printf("共有 %d 中方法 .\n\n",count);

return 0;
}

2. 分析解读 :

(由于这个排版和本人已经排版好的笔记不是很统一, 所以下面采用图片的方式展示)

递归版"八皇后问题"的详细解读