主题:[讨论]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]
#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]