数据结构课程设计n皇后问题的代码实现

注释详细，利用了两种方法实现n皇后问题，可以直接作为数据结构课程设计的代码。

#include 
#include
#include
#include

using namespace std;

//全局变量
const int MAX = 30;  //最多的皇后个数
int col[MAX+1];      //表示放置后每个皇后的列数
int number = 0;    //解的数目


//输出一个解此解以数字的方式显示出来
void printNumber（int n）
{
    number++;//每次输出一个解 数目加一

    cout<<“第“;
    cout.width（2）;
    cout<    //输出
    for（int i=1; i<=n; i++）
    {

        cout<    }
    cout <}

//输出一个解此解以图形的方式显示出来
void printPicture（int n）
{
    number++;//每次输出一个解 数目加一
    char table[n+1][n+1]; //表示棋盘

    cout<<“第“;
    cout.width（2）;
    cout<    //棋盘的初始化和输出
    for（int j=1; j<=n; j++）
    {
        for（int k=1; k<=n; k++）
        {
            if（col[j] == k）
                table[j][k] = ‘-‘;//此解对应的棋盘的布局中皇后的位置
            else
                table[j][k] = ‘*‘;   //没有放置皇后的用黑块表示

            //输出
            cout<<“ “<
        }
        cout<    }

}

//在（row cols）位置是否可以放置一个皇后
bool ifFind（int row int cols）
{
    //对前row-1 行所放置的皇后进行一一比较
    for（int i=1; i         //如果前row-1 行所放置的某一个皇后的列数与cols相同或者
        //和（row，cols）在同一对角线上，则（row cols）位置不能放置皇后
        if（col[i]==cols || （abs（i-row））==abs（col[i]-cols））
            return false;
    //没有产生相同列数和同一对角线
    return true;
}

//放置皇后，采用回溯法
//第k个皇后放在第k行，需要放 n个皇后
void placeBack（int k  int n）
{
    //结束条件
    if（k>n）
    {
         printNumber（n）;  //打印最终结果的数据表示
//        printPicture（n）;   //打印图形
    }

    else
        //在第k行穷举所有位置，逐一试探第k行的所有列
        for（int i=1; i<=n; i++ ）
        {
            //判断第i列是否可以，如果可以则递归调用place（）
            //继续在k+1行穷举
            if（ifFind（k i）） //在（k，i）位置是否可以放置皇后
            {
                col[k] = i;
                placeBack（k+1 n）;//递归调用place（），进行下一行的试探和放置
            }

        }

}

//优化后的回溯方法第一步应该先初始化col[]数组
void initializationCol（int n）
{
    number = 0;   //解的数目
    //将每一行先填上一个皇后，保证每个皇后不在同一列
    for（int i=1; i<=n; i++）
        col[i] = n-i+1;
}

//放置皇后，采用优化的回溯方法
//思想是全排列，先将皇后放好一个位置，保证没有同行和同列的
//然后交换皇后，从前往后交换，实现没有相同对角线的
void placeOther（int *theCol int n int beginRow）
{
    //判断输入的变量是否有效
    if（theCol == NULL || n>30）
        cout<<“变量有误~“;
    //建两个数组来判断对角线上是不是冲突
    bool leftDown[2*n+1];  //用来判断从左下到右上这个对角线方向是不是已经有皇后
    bool leftUp[2*n+1];    //用来判断从左上到右上下这个对角线方向是不是已经有皇后
    //初始化bool数组
    memset（leftDownfalsesizeof（leftDown））;
    memset（leftUpfalsesizeof（leftUp））;
    //如果已经没有了要交换的皇后，也就是一个已经确定的顺序
    if（（beginRow == n））
    {
        bool canPrint = true;
        for（int i=1; i<=n; i++）
        {
            //如果从第一行开始，每一个皇后所在的主对角线和副对角线上已经有其他皇后
            if（leftDown[i+theCol[i]] || leftUp[n+i-theCol[i]]）
            {
                //不能打印出来
                canPrint = false;
                //因为这个顺序不满足要求，所以将判断的数组重置
                leftDown[i+theCol[i]] = leftUp[n+i-theCol[i]] = false;
                //跳出循环
             

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2017-03-05 09:03  nQueen\
     目录           0  2017-02-26 10:24  nQueen\bin\
     目录           0  2017-03-02 21:40  nQueen\bin\Debug\
     文件     1064404  2017-03-02 21:40  nQueen\bin\Debug\nQueen.exe
     文件        5220  2017-03-02 21:40  nQueen\main.cpp
     文件        1327  2017-02-28 01:40  nQueen\newWay.cpp
     文件        1103  2017-02-28 02:08  nQueen\nQueen.cbp
     文件         178  2017-03-02 18:43  nQueen\nQueen.depend
     文件         361  2017-03-05 09:03  nQueen\nQueen.layout
     目录           0  2017-02-26 10:24  nQueen\obj\
     目录           0  2017-03-02 21:40  nQueen\obj\Debug\
     文件       20175  2017-03-02 21:40  nQueen\obj\Debug\main.o
     文件        3070  2017-02-28 01:41  nQueen\obj\Debug\newWay.o