问题：八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于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语言算法，八皇后问题，回溯算法】
推荐阅读
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- 【C】题目|【C语言】题集 of ⑥
- 单片机|自学单片机好找工作吗（会单片机能找什么工作？）
- 单片机|keil把源代码生成lib的方法
- c语言|一文搞懂栈(stack)、堆(heap)、单片机裸机内存管理malloc
- c语言|C语言初期学习遇到的特殊点 【三子棋详解】【初学者福音，详细总结，复习能手】
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- 个人理解|【C语言基础之类型转换】
- c语言|【C语言】自定义类型 结构体 枚举 联合
- 学习分享|【C语言函数基础】