锐客网

  1. 首页 > it技术 > >

八皇后问题回溯非递归算法的C语言实现（文中是C语言的基本语法）

【八皇后问题回溯非递归算法的C语言实现（文中是C语言的基本语法）】之前在CSDN的博客上看到过大神们写的回溯非递归代码，无奈C语言属于初级阶段无法理解位运算符等，所以自己写了一个，此算法虽不算简洁，但看完应该就能理解算法所要表达的思想。小弟的第一篇博客，大神勿喷

#include int chess[8][8]; //定义8*8的棋盘，其中0表示该位置没有皇后，1表示该位置有皇后 int count = 0; int judge(int r,int c)//这个是判断函数，判断此行此列能不能放皇后 { int i; int j; for(i=0; i<8; i++)//检查当前位置所在列有没有其他的皇后 { if(chess[i][c]) return 0; } for(i=r,j=c; i>=0&&j>=0; i--,j--)//检查当前位置的左上斜线有没有其他皇后 { if(chess [i][j]) return 0; } for(i=r,j=c; i>=0&&j<8; i--,j++)//检查当前位置的右上斜线有没有皇后 { if(chess[i][j]) return 0; } return 1; //全部都没有，说明此位置可以放皇后，返回1 }void eightQueen() { int stack[9] = {0,0,0,0,0,0,0,0,0}; //此处定义为9个，此数组实际为栈，用来保存每一行已经搜索的列，其中第一行下标为0 int top = 0; int i; while(top>=0)if (top == 8)//注意top = 0为第一行，=8时已为第九行 { count++; //用来记八皇后的个数 top--; //返回到第八行 stack[top]++; } else { for(; stack[top]<8; stack[top]++) { if(judge(top,stack[top])) { chess[top][stack[top]] = 1; break; } }if(stack[top] < 8 && top <8) { top++; } else if (stack[top] == 8 && top <8) { for (i=0; i<8; i++) { chess[top][i] = 0; //此处两行是将当前行和即将回溯到的那一行清空。 chess[top-1][i] = 0; } stack[top--] = 0; //因为要回溯到上一行，所以此行的栈记录要变为零，下次到这一行时继续从第一个元素判断 stack[top]++; //上一行的元素加1，不加1还是判断的是之前的位置，会死循环 } } } int main() { int i ; int j ; for(i=0; i<8; i++)//初始化棋盘 { for(j=0; j<8; j++) { chess[i][j] = 0; } }eightQueen(); printf("%d",count); //打印出一共有多少种摆法 return 0; }


    推荐阅读


    上一篇：一些C基础的小编程题目

    下一篇：stm32F4 配置串口+DMA 接收不定长数据 串口空闲中断