用栈解决N皇后问题（C语言）
点击上方蓝字关注"程序员Bob"呀~
孩子不是图画练习册，你不能随心所欲涂上你想要的颜色。
——《追风筝的人》
问题描述：输入一个整数n，输出对应的n皇后问题的解的个数
在解决N皇后问题之前，我们得知道皇后问题的来源。
首先最开始的是八皇后问题，是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，也是回溯算法的典型案例。
起初问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。
当然，随着计算机的发展，现在我们可以用程序来解决此类问题。
下面代码用到栈的知识，用栈装载了每一行放置的皇后的坐标，通过入栈与出栈，实现回溯。栈的结构为双链表结构。
源代码如下：
typedef struct Queen{int x;int y;}Queen;typedef struct ListNode{//建立结点Queen q;struct ListNode *Next;//指向前一个结点struct ListNode *Last;//指向后一个结点}ListNode;typedef struct List {//建立双向链表struct ListNode *header;struct ListNode *trailer;int _size;}List;void CreateList(List *l);void InsertList(List *l,Queen e);Queen PopList(List *l);void InsertBefore(int i,Queen e,List *l);void CreateList(List *l){l->_size=0;l->header= (ListNode*)malloc(sizeof(ListNode));l->trailer=(ListNode*)malloc(sizeof(ListNode));l->header->Next=l->trailer;l->header->Last=NULL;l->trailer->Last=l->header;l->trailer->Next=NULL;}void InsertList(List *l,Queen e){//在尾结点之前插入数据ListNode *np=(ListNode*)malloc(sizeof(ListNode));np->q.x=e.x;np->q.y=e.y;np->Next=l->trailer;np->Last=l->trailer->Last;l->trailer->Last->Next=np;l->trailer->Last=np;l->_size++;}void InsertBefore(int i,Queen e,List *l){//在第i项前插入eint j;ListNode *p=l->header->Next;for(j=0;j<i;j++){p=p->Next;//定位到第几项}ListNode *np=(ListNode*)malloc(sizeof(ListNode));np->q.x=e.x;np->q.y=e.y;np->Next=p;np->Last=p->Last;p->Last->Next=np;p->Last=np;l->_size++;}void PushList(List *l,Queen e){//入栈ListNode *np=(ListNode*)malloc(sizeof(ListNode));np->q.x=e.x;np->q.y=e.y;np->Last=l->header;np->Next=l->header->Next;np->Next->Last=np;l->header->Next=np;l->_size++;}Queen PopList(List *l){//出栈ListNode *now=l->header->Next;Queen old=now->q;now->Next->Last=now->Last;l->header->Next=now->Next;free(now);l->_size--;return old;}int placeQ(int N){int solution_n = 0;int i;List solution;CreateList(&solution);Queen q;q.x=0;q.y=0;int *xarray=(int*)calloc(N,sizeof(int));int *yarray=(int*)calloc(N,sizeof(int));int *sumarray=(int*)calloc(2*N,sizeof(int));int *diffarray=(int*)calloc(2*N,sizeof(int));for(i=0;i<N;i++){xarray[i]=yarray[i]=0;}for(i=0;i<N*2;i++){sumarray[i]=diffarray[i]=0;}do{if(N<=solution._size ||N<=q.y) {Queen tmp = PopList(&solution);q.x = tmp.x;q.y = tmp.y;xarray[q.x]=0;//防止行冲突yarray[q.y]=0;//防止列冲突sumarray[q.x+q.y]=0;//存储信息，防止对角线冲突diffarray[q.x-q.y+N]=0;//防止另一条对角线冲突q.y++;}else {while ((q.y < N) && ((xarray[q.x] == 1) || (yarray[q.y] == 1) || \(sumarray[q.x + q.y] == 1) || (diffarray[q.x - q.y + N]) == 1)) {q.y++;}if (N > q.y) {PushList(&solution, q);xarray[q.x] = 1;yarray[q.y] = 1;sumarray[q.x + q.y] = 1;diffarray[q.x - q.y + N] = 1;if (N <= solution._size) {solution_n++;}q.x++;q.y = 0;}}}while((q.x>0)||(q.y<N));return solution_n;}int main() {int num;scanf("%d",&num);//scanf_s("%d",&num); //进行边界检查,VS支持//printf_s("%d",placeQ(num));//检查字符是否有效printf("%d",placeQ(num));return 0;}
运行结果如下：
最后的话：刷题要找自己的不足，然后去专攻。
往期推荐：
2020-12-01
2020-11-28
2020-11-26
为你,千千万万遍.
关注程序员Bob公众号,与你一起终生学习
本文分享自微信公众号 - 程序员Bob（gh_8a1a1530d0bf）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
