本文共 3550 字，大约阅读时间需要 11 分钟。

c语言求解n皇后问题

问题描述：

输入一个整数n，输出对应的n皇后问题的解的个数

准备工作0：大致思路

对于n皇后问题，显然采用回溯法：逐行放置皇后，对于某一行来说，依次遍历所有位置，直到在该行找到一个合法的位置把皇后放入其中；若在该行找不到这样的合法位置，就回溯到上一行的皇后，将其继续移动，直到在当前行找到下一个合法位置。若已经到达最后一行，且找到了放置皇后的合法位置，那么解的个数加一，并再次回溯。

准备工作1：数据结构（栈）实现

由于采用迭代法而不是传统的递归法解决这个问题，算法需要我们显式地维护一个栈，而这个栈，装载了每一行放置的皇后的坐标，通过入栈与出栈，实现回溯。这个栈的结构基于双向链表，大家可以看我写的上一篇。

话不多说，上代码：

struct Queen {
   //定义皇后的坐标 int x; int y;};

struct ListNode {
    Queen q; ListNode* Next; ListNode* Last;};struct List {
    ListNode* header; ListNode* trailer; int _size;};void CreateList(List* l)//build the list{
    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{
    ListNode* p = l->header->Next; for (int 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;}

可以明显地看出，这里实现地栈具有鲜明的双向链表的特征，实际上，在面向对象语言中可以进一步封装，使得对于栈的某些操作不合法（如访问非栈顶元素），不过既然是c语言。就没必要这样了

正式开始：n皇后问题

先上代码：

int placeQ(int N){
    int nsolution = 0; 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 (int i = 0; i < N; i++)  xarray[i] = yarray[i] = 0; for (int i = 0; i < 2 * N; 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)     nsolution++;    q.x++;    q.y = 0;   }  } } while ((0 < q.x) || (q.y < N)); return nsolution;}

思路如下：

我们的想法，就是对于n*n的棋盘，从第一行第一列开始放置皇后，然后在第二行，从左至右，找到第一个可以放置皇后的位置并放置一个皇后。那么什么时候会遇到一点问题呢？一种情况是，我在某一行找不到放置皇后的合法位置了；另一种情况是，每一行都放置了一个皇后，此时已经构成了一个解，需要寻找下一个解。对于第一种情况，我们需要把当前行的上一行的皇后移除，在代码上的表现，就是把q的位置设置为上一行的皇后位置并从这个位置继续向右，找到第一个可以放置皇后的位置，并放置之；对于第二种情况，其实前半部分处理与第一种情况相同，但是不要忘记在返回的nsolution加上一（因为此时已经有了一个解）

调用函数

int main(){
    int num; scanf_s("%d", &num); printf_s("%d", placeQ(num)); return 0;}

输入与输出：

BONUS

当然，考试的时候可能直接要求输入一个n，返回对应的n皇后问题的解，如果是黑盒子测评的话，你可以把答案背下来，这也是oj测评的特殊技巧。

n	n皇后解的数量
1	1
2	0
3	0
4	2
5	10
6	4
7	40
8	92
9	352
10	724
11	2680
12	14200
13	73712
14	365596
15	2279184

完

转载地址：http://czwai.baihongyu.com/