数据结构课程设计-用堆栈求解n皇后问题_用栈求解n皇后问题

摘  要

N皇后问题是一个经典的问题，在一个N×N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。很明显，皇后的位置是通过搜索出来的，每个位置进行搜索，N皇后问题是回溯法的典型算法。

关键词：数据结构  n皇后  堆栈  回溯法  非递归

第二章  课设实现过程

在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。

这个问题要求把n个皇后放在一个n×n的棋盘上，使得任何两个皇后都不能相互攻击，即它们不能同行，不能同列，也不能位于同一条对角线上。对于n=1，问题的解很简单，而且很容易看出对于n=2和n=3来说，这个问题是无解的。所以我们考虑4皇后问题，并用回溯法对它求解。我们从空棋盘开始，然后把皇后1放在它所在行的第一个可能位置上，也就是第一行第一列。对于皇后2，在经过第一列和第二列的失败尝试之后，我们把它放在第一个可能的位置，就是格子（2,3），位于第二行第三列的格子。这被证明是一个死胡同，因为皇后3将没有位置可放。所以，该算法进行回溯，把皇后2放在下一个可能位置（2,4）上。这样皇后3就可以放在（3,2），这被证明是另一个死胡同。该算法然后就回溯到底，把皇后1移到（1,2）。接着皇后2到（2,4），皇后3到（3,1），而皇后4到（4,3），这就是该问题的一个解。

回溯法实现的主要思路首先是把棋盘的横坐标定为i，纵坐标定为j，i和j的取值范围是从1到n。当某个皇后占了位置（i,j）时，在这个位置的垂直方向、水平方向和斜线方向都不能再放其他皇后了。

下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘：

1) 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列

2) 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步

3) 在当前位置上满足条件的情形：

在当前位置放一个皇后，若当前行是最后一行，记录一个解；

若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；

若当前行是最后一行，当前列不是最后一列，当前列设为下一列；

若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；以上返回到第2步

4) 在当前位置上不满足条件的情形：若当前列不是最后一列，当前列设为下一列，返回到第2步;若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步; 

把棋盘存储为一个N维数组，数组中第i个元素的值代表第i行的皇后位置，这样便可以把问题的空间规模压缩为一维，在判断是否冲突时也很简单，首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等 。这样某个位置是否可以放置皇后的问题已经解决。 

非递归方法的一个重要问题时何时回溯及如何回溯的问题。程序首先对N行中的每一行进行探测，寻找该行中可以放置皇后的位置，具体方法是对该行的每一列进行探测，看是否可以放置皇后，如果可以，则在该列放置一个皇后，然后继续探测下一行的皇后位置。如果已经探测完所有的列都没有找到可以放置皇后的列，此时就应该回溯，把上一行皇后的位置往后移一列，如果上一行皇后移动后也找不到位置，则继续回溯直至某一行找到皇后的位置或回溯到第一行，如果第一行皇后也无法找到可以放置皇后的位置，则说明已经找到所有的解程序终止。如果该行已经是最后一行，则探测完该行后，如果找到放置皇后的位置，则说明找到一个结果，打印出来。但是此时并不能再此处结束程序，因为我们要找的是所有N皇后问题所有的解，此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。

程序代码(C语言)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MaxSize 100
typedef struct
{
    int data[MaxSize];	//data[i]存放第i个皇后的列号
    int top;			//栈顶指针
} StType;				//定义顺序栈类型
int count=0;
int place(StType st,int i,int j)  //测试(i,j)是否与1～i-1皇后有冲突
{
    int a=0;         //a为函数的返回值
    int k=1;
    if (i==1)
    {
        a=1;
        return a;	//放第一个皇后时没有冲突
    }
    while (k<=i-1)			//j=1到k-1是已放置了皇后的列
    {
        if ((st.data[k]==j)||(fabs(j-st.data[k])==fabs(i-k)))
        {
            a=0;
            return a;
        }
        else
            k++;
    }
    a=1;
    return a;
}
void queen(int n)					//求解n皇后问题
{
    int i,j,k;
    int find=0;
    StType st;						//定义栈st
    st.top=0;						//初始化栈顶指针
    st.top++;						//将(1,1)进栈
    st.data[st.top]=1;
    while (st.top>0)				//栈不空时循环
    {
        i=st.top;					//当前皇后为第i个皇后
        if (st.top==n)				//所有皇后均放好,输出一个解
        {
            printf("第%d个解：",++count);
            for (k=1; k<=st.top; k++)
                printf("(%d,%d) ",k,st.data[k]);
            printf("\n");
        }
        find=0;
        for (j=1; j<=n; j++)
            if (place(st,i+1,j))	//在i+1行找到一个放皇后的位置(i+1,j)
            {
                st.top++;
                st.data[st.top]=j;
                find=1;
                break;
            }
        if (find==0)			//在i+1行找不到放皇后的位置,回溯
        {
            while (st.top>0)
            {
                if (st.data[st.top]==n)	//本行没有可放位置,退栈
                    st.top--;
                for (j=st.data[st.top]+1; j<=n; j++)	//在本行找下一个位置
                    if (place(st,st.top,j))
                    {
                        st.data[st.top]=j;
                        break;
                    }
                if (j>n)				//当前皇后在本行没有可放的位置
                    st.top--;			//退栈
                else					//本行找到一个位置后退出回溯
                    break;
            }
        }
    }
}
 
int main()
{
    int n;
    printf(" 皇后问题(n<20) n=");
    scanf("%d",&n);
    printf(" %d皇后问题求解如下：\n",n);
    queen(n);
    printf("\n");
    return 0;
}

程序代码（python）

def conflict(state, nextColumn): #冲突函数
    nextRow = rows = len(state)  
    for row in range(rows): 
        column = state[row]
        if abs(column - nextColumn) in (0, nextRow - row):   #如果列相同或列数差等于行数差（位于同一对角线上），则冲突，否则不冲突。         
            return True
    return False
def queens(num, state=()):   #主函数，for循环对每个皇后位置使用冲突函数进行判断，如果到state到倒数第二行，此时最后一行不冲突，记录位置。
    for i in range(num):  
        if not conflict(state, i):  
            if len(state) == num - 1:  
                yield (i,)
            else:  
                for result in queens(num, state + (i,)):
                    yield (i,) + result
 
def mapprint(solution):      #定义一个map函数生成图，对于放置皇后的列前用.表示，皇后处用Q表示，后面到最后一列用.表示。
    def line(i, length=len(solution)): 
        return ' . ' * (i) + ' Q ' + ' . ' * (length - i - 1) 
    for i in solution:
        print(line(i))
n = input();#读入未知量n。
n = int(n);
solutions = queens(n)#
for i, j in enumerate(solutions):#for循环enumerate函数打出（第几个解，解）。
    print("第%d种解决方案:" % (i + 1), j)
    mapprint(j)