回 帖 发 新 帖 刷新版面

主题:[讨论]8皇后问题

8皇后问题的代码,我已经基本编写完成,但是还有一些小问题([color=FF0000]非逻辑性问题,出问题的地方已用红色标出[/color]),希望高手指教,代码如下:
#include "math.h" 
#include "iostream.h"

#define QueenMax 4
#define TRUE     1
#define FALSE    0

/*
 *   棋子的数据结构
 */
struct point
{
    int row;
    int col;
};

/*
 *   棋盘的数据结构
 */
struct Checkerboard
{
    struct point QueenMatrix[QueenMax];
};

/*
 *   堆栈的数据结构
 */
struct stack
{
    int    size;               //堆栈的大小
    struct Checkerboard *base; //栈底指针
    struct Checkerboard *top;  //栈顶指针
};

/*
 *   初始化棋盘
 */
void initCheckerboard(struct point QueenMatrix[])
{
    for(int i =0; i < QueenMax; i++)
    {
        QueenMatrix[i].row = -1;
        QueenMatrix[i].col = -1;
    }
}

/*
 *    判断当前位置第row行,第col列是否合法
 */
bool invalid(struct point QueenMatrix[], int row, int col)
{
    for(int i =0; i < QueenMax; i++)
    {
        /*
         *    棋盘上没有放置棋子,或者已经放置的棋子都已经判断为合法,
         *    则返回FALSE
         */
        if (0 > QueenMatrix[i].row)
        {
            return FALSE;
        }

        if     (QueenMatrix[i].row == row       //当前的位置与已经放置的棋子处在同一行 
         ||  QueenMatrix[i].col == col       //当前的位置与已经放置的棋子处在同一列
         //当前的位置与已经放置的棋子处在同一对角线
         || abs(QueenMatrix[i].row - row) == abs(QueenMatrix[i].col - col)
         )
        {
            return TRUE;
        }
    }
    return FALSE;
}

/*
 *    在第row行,第col列放置一个棋子
 */
void setCurentPosition(struct point QueenMatrix[], int row, int col)
{
    for(int i =0; i < QueenMax; i++)
    {
        if (0 > QueenMatrix[i].row)
        {
            QueenMatrix[i].row = row;
            QueenMatrix[i].col = col;
            break;
        }
    }
}

/*
 *    将第row行,第col列原先放置的一个棋子拿掉
 */
void clearJustPosition(struct point QueenMatrix[], int row, int col)
{
    //棋盘上还没有放置棋子
    if (0 > QueenMatrix[0].row)
    {
        return;
    }

    //棋盘上的棋子放了一部分
    int i;
    for(i = 0; i < QueenMax; i++)
    {
        if (0 > QueenMatrix[i].row)
        {
            QueenMatrix[i - 1].row = -1;
            QueenMatrix[i - 1].col = -1;
            return;
        }
    }

    //棋盘上的所有棋子都放好了
    QueenMatrix[i - 1].row = -1;
    QueenMatrix[i - 1].col = -1;
}

/*
 *    初始化堆栈,存放棋盘的各个状态
 */
void initStack(struct stack &s)
{
    s.base = new struct Checkerboard;

    for (int i = 0; i < QueenMax; i++)
    {
        s.base->QueenMatrix[i].row = -1;
        s.base->QueenMatrix[i].col = -1;
    }

    s.top  = s.base;
    s.size = 0;
}

/*
 *    将状态为status的棋盘压入堆栈
 */
void push(struct stack &s, Checkerboard *status)
{
    for (int i = 0; i < QueenMax; i++)
    {
        s.top->QueenMatrix[i].row = status->QueenMatrix[i].row;
        s.top->QueenMatrix[i].col = status->QueenMatrix[i].col;
    }
    s.top  = s.top + 1;
    s.size = s.size + 1;
}

/*
 *    弹出栈顶元素
 */
void pop(struct stack &s, Checkerboard *status)
{
    s.top  = s.top - 1;
    s.size = s.size - 1;
    for (int i = 0; i < QueenMax; i++)
    {
        status->QueenMatrix[i].row = s.top->QueenMatrix[i].row;
        status->QueenMatrix[i].col = s.top->QueenMatrix[i].col;
    }
}

/*
 *    输出可行性结果
 */

void outputResult(struct point QueenMatrix[], int n)
{
    for(int i = 0; i < n; i++)
    {
        cout<<"("<<QueenMatrix[i].row<<","<<QueenMatrix[i].col<<")"<<" ";
    }
    cout<<endl;
}
/*
 *    QueenMatrix -> status
 */
void copy(struct Checkerboard *status, struct point QueenMatrix[])
{
    for(int i = 0; i < QueenMax; i++)
    {
        status->QueenMatrix[i].row = QueenMatrix[i].row;
        status->QueenMatrix[i].col = QueenMatrix[i].col;
    }
}

/*
 *   主函数
 *   8皇后问题,即:在8*8格的国际象棋上摆放8个皇后,
 *   使其不能互相攻击,即任意两个皇后都不能处于同一行、
 *   同一列或同一斜线上,问有多少种摆法。
 *   在这个函数中,将其延伸为n后问题。
 */

void nQueen(int n)
{
    struct point QueenMatrix[QueenMax];
    initCheckerboard(QueenMatrix);
    struct stack QueenStack;
    initStack(QueenStack);
    int row = 0;
    int col = 0;
    struct Checkerboard *status = new struct Checkerboard;
    do
    {
        while (row < n)
        {
            while (col < n)
            {
                if (TRUE == invalid(QueenMatrix, row, col))
                {
                    //获取下一个棋子应该放置的位置
                    col = col + 1;
                }
                else
                {
                    setCurentPosition(QueenMatrix, row, col);
                    copy(status, QueenMatrix);
                    push(QueenStack, status);
                    row = row + 1;
                    col = 0;
                    break;
                }
            }
            if (col >= n)
            {
                if (0 == QueenStack.size)
                {
                    return;
                }
                pop(QueenStack, status);
                for(int i = 0; 0 <= status->QueenMatrix[i].row; i++);
                row = status->QueenMatrix[i - 1].row;
                col = status->QueenMatrix[i - 1].col;
                clearJustPosition(QueenMatrix, row, col);
                col = col + 1;
                while (col < n && TRUE == invalid(QueenMatrix, row, col))
                {
                    col = col + 1;
                }
                if (col < n)
                {
                    setCurentPosition(QueenMatrix, row, col);
                    copy(status, QueenMatrix);
                    push(QueenStack, status);
                    row = row + 1;
                    col = 0;
                }
            }
        }
        [color=FF0000][size=3]//此处有问题,在这里设个断点,可以看到数组QueenMatrix的值,但是函数中想通过cout输出,程序确报错。而在main函数中单独调用此函数,详见nQueen(QueenMax);以下的注释掉的代码,是没有问题的,所以不知道问题出在哪里,希望高手指教[/size][/color]
        outputResult(QueenMatrix, QueenMax);
        pop(QueenStack, status);
        for(int i = 0; 0 <= status->QueenMatrix[i].row; i++);
        row = status->QueenMatrix[i - 1].row;
        col = status->QueenMatrix[i - 1].col;
        clearJustPosition(QueenMatrix, row, col);
        col = col + 1;
        while (col < n && TRUE == invalid(QueenMatrix, row, col))
        {
            col = col + 1;
        }
    }while(0 != QueenStack.size);
}

int main()
{
    nQueen(QueenMax);
    return 0;
    /*
    struct point QueenMatrix[QueenMax];
    initCheckerboard(QueenMatrix);
    outputResult(QueenMatrix, QueenMax);
    */
}[color=FF0000][/color]

回复列表 (共5个回复)

沙发

好像没问题哦?我编译运行都正常

板凳

可能是我的vc6.0有问题?郁闷!这个程序的结果正确吗?
还有代码有哪些需要改正或者改进的地方,希望大家各抒己见,不吝赐教!

3 楼

调试看看不就知道咯?

4 楼

八皇后问题只用一个栈就可以解决问题...

5 楼

bcahzvip,你看见我写得红字了吗?不要什么问题看都不看就说调试一下,好吗?

我来回复

您尚未登录,请登录后再回复。点此登录或注册