用栈解决N皇后问题（C语言）
点击上方蓝字关注"程序员Bob"呀~ 孩子不是图画练习册，你不能随心所欲涂上你想要的颜色。 ——《追风筝的人》 问题描述：输入一个整数n，输出对应的n皇后问题的解的个数 在解决N皇后问题之前，我们得知道皇后问题的来源。 首先最开始的是八皇后问题，是由国际西洋棋棋手马克斯·贝瑟尔于1848年提出的问题，也是回溯算法的典型案例。 起初问题表述为：在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。 当然，随着计算机的发展，现在我们可以用程序来解决此类问题。 下面代码用到栈的知识，用栈装载了每一行放置的皇后的坐标，通过入栈与出栈，实现回溯。栈的结构为双链表结构。 源代码如下： #include <stdio.h>#include <stdlib.h>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项前插入e int 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;} 运行结果如下： 最后的话：刷题要找自己的不足，然后去专攻。 往期推荐： 十一月碎碎念 || 假如时间只剩31天 2020-12-01 《流浪猫鲍勃》：一人一猫，彻底温暖了整个冬天 2020-11-28 来学Python啦，浅谈函数 2020-11-26 为你,千千万万遍. 关注程序员Bob公众号,与你一起终生学习 一键三连，就差你了 本文分享自微信公众号 - 程序员Bob（gh_8a1a1530d0bf）。如有侵权，请联系 support@oschina.cn 删除。本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
