主题：[原创]国际象棋的马踏遍棋盘的演示程序[附源码]
llehotnwod
[专家分：330] 发布于 2006-06-04 10:04:00
> /////////////////////////////////////////////////////
> 问题描述:
> 设计一个国际象棋的马踏遍棋盘的演示程序.
> /////////////////////////////////////////////////////
> 基本要求:
> 将马随机放在国际象棋的8X8棋盘Board[8][8]的某个方格中,马
> 按走棋规则进行移动.
> 要求每个方格只进入一次,走遍棋盘上全部64个方格.
> 编制非递归程序,求出马的行走路线,
> 并按求出的行走路线,将数字1,2,3,...,64依次填入一个
> 8X8的方阵中去,输出之.
> /////////////////////////////////////////////////////
> 测试数据:
> 由用户指定.可自行指定一个马的初始位置(i,j),0<=i,j<=7
> /////////////////////////////////////////////////////
> 选作内容:
> 1)求出从某一起点出发的多条以至全部行走路线.
> 2)探讨每次选择位置的"最佳策略",以减少回溯的次数.
> 3)演示寻找行走路线的回溯过程.
回复列表 （共4个回复）
沙发
llehotnwod [专家分：330] 发布于 2006-06-04 10:05:00
[code]
///////////////////////////////////////
////////////// minestack.h /////////////
///////////////////////////////////////
#ifndef _stack_h_mine
#define _stack_h_mine
#include <assert.h>
#include <unistd.h>
#include <stdbool.h>
#define __minedebug
/*
********* stack *******
*/
extern const int N;
typedef struct _stacknode{
int _n;
int _x,_y;
int *_loc;
struct _stacknode *_pri;
struct _stacknode *_next;
}*stacknode;
typedef struct _stack{
ssize_t _size;
stacknode _top;
}*stack;
/*
* ********************
*/
stack stackcreat (void);
bool stackpush (stack, int (*)[N],int *,int *,int *);
bool stackpop (stack, int (*)[N],int *,int *,int *);
bool stackempty (const stack);
#endif [/code]
板凳
llehotnwod [专家分：330] 发布于 2006-06-04 10:06:00
[code]
////////////////////////////////////////
/////////////// minestack.c
//////////////////////////////////////////
#include <stdio.h>
#include "minestack.h"
const int N=8;
stack
stackcreat (void)
{
stack s;
assert( NULL != (s=(stack)malloc(sizeof(struct _stack))) );
s->_size = 0;
s->_top = NULL;
return s;
}
static int *
_loc(int (*map)[N],const int x,const int y)
{
const int _x[8]={ -2, -1, 1, 2, 2, 1, -1, -2 };
const int _y[8]={ 1, 2, 2, 1, -1, -2, -2, -1 };
int *rP;
int i;
assert( NULL != (rP=(int *)malloc(sizeof(int)*(8*2+1))) );
for(i=0,rP[0]=0; i<8; ++i){
int tX = _x[i] + x;
int tY = _y[i] + y;
if( tX>=0 && tX<N && tY>=0 && tY<N && (map[tX][tY]==0) ){
rP[0]++;
rP[ rP[0]*2-1 ] = tX;
rP[ rP[0]*2 ] = tY;
}
}
if( rP[0] == 0 ){
free( rP );
rP = NULL;
}
return rP;
}
static bool
_getloc(int *const loc,int *x,int *y)
{
if( 0 == loc[0] )
return false;
else{
*x = loc[ loc[0]*2 - 1 ];
*y = loc[ loc[0]*2 ];
loc[0]--;
}
return true;
}
static void
_print(int (*map)[N])
{
int i,j;
for(i=0; i<N; ++i){
for(j=0; j<N; ++j){
fprintf(stdout,"%4d",map[i][j]);
}
fprintf(stdout,"\n");
}
fprintf(stdout,"\n");
}
bool
stackpush (stack s, int (*map)[N],int *x,int *y,int *n)
{
stacknode node=(stacknode)malloc(sizeof(struct _stacknode));
assert( node != NULL );
int *p;
#ifdef _minedebug
fprintf(stderr,"calling stackpush!!\n");
#endif
if( *n == N*N ){
map[*x][*y] = *n;
_print( map );
map[*x][*y] = 0;
free( node );
return false;
}
map[*x][*y] = *n;
if( NULL == (p=_loc(map,*x,*y)) ){
map[*x][*y] = 0;
free( node );
return false;
}
node->_n = *n; node->_x = *x; node->_y = *y; node->_loc = p;
if( stackempty(s) == true ){
s->_top = node;
}else{
node->_pri = s->_top;
s->_top->_next = node;
s->_top = node;
}
++s->_size;
map[*x][*y] = *n;
assert( true == _getloc(s->_top->_loc,x,y) );
++(*n);
return true;
}
bool
stackpop (stack s, int (*map)[N],int *x,int *y,int *n)
{
stacknode sp;
#ifdef _minedebug
fprintf(stderr,"calling stackpop!!\n");
#endif
if( true == stackempty(s) ){
assert( false != _getloc(s->_top->_loc,x,y) );
map[*x][*y] = *n;
return false;
}
map[*x][*y] = 0;
*n = s->_top->_n;
*x = s->_top->_x;
*y = s->_top->_y;
map[*x][*y] = *n;
if( false == _getloc(s->_top->_loc,x,y) ){
free( s->_top->_loc );
s->_top->_loc = NULL;
sp = s->_top->_pri;
free( s->_top );
s->_top = sp;
--(s->_size);
return false;
}
map[*x][*y] = ++*n;
return true;
}
bool
stackempty (const stack s)
{
return (s->_size)?false:true;
}
[/code]
3 楼
llehotnwod [专家分：330] 发布于 2006-06-04 10:06:00
[code]
////////////////////////////////////////////
////////////////// main.c
////////////////////////////////////////////
#include <stdio.h>
#include "minestack.h"
extern const int N;
static void
mapprint(int (*map)[N])
{
int i,j;
for(i=0; i<N; ++i){
for(j=0; j<N; ++j){
fprintf(stdout,"%4d",map[i][j]);
}
putchar('\n');
}
putchar('\n');
}
int
main(int argc, char **argv)
{
int gN=1,gX,gY;
int gMap[N][N];
stack gStack=stackcreat();
/**********************/
if( argc != 3 ){
fprintf(stderr,"Usage:./a.out <X> <Y>\n");
exit(-1);
}
gX = atoi( argv[1] );
gY = atoi( argv[2] );
if( gX<0 || gX>N-1 || gY<0 || gY>N-1 ){
fprintf(stderr,"error! 0 <= (X,Y) < %d",N);
exit(-1);
}
/**********************/
do{
int i,j;
for(i=0; i<N; ++i){
for(j=0; j<N; ++j){
gMap[i][j] = 0;
}
}
}while(0);
/**********************/
assert( false != stackpush(gStack,gMap,&gX,&gY,&gN) );
while( stackempty(gStack) != true ){
/****************/
#ifdef _minedebug
fprintf(stderr,"gN=%-4d,gX=%-4d,gY=%-4d\n",gN,gX,gY);
{
int i,j=gStack->_top->_loc[0];
fprintf(stderr,"i[0]=%d:",j);
for(i=1; i<j*2+1; ++i ){
fprintf(stderr,"%3d%", gStack->_top->_loc[i]);
}
putchar('\n');
}
mapprint(gMap);
getchar();
#endif
/****************/
if( false == stackpush(gStack,gMap,&gX,&gY,&gN) ){
while(true != stackpop(gStack,gMap,&gX,&gY,&gN))
;
}
}
free( gStack );
exit(0);
}
[/code]
4 楼
llehotnwod [专家分：330] 发布于 2006-06-04 10:09:00
如果要查看每步程序的棋盘状态
只需将
minestack.h文件中的
#define __minedebug 改为#define _minedebug 即可了
更多的源码起申请http://groups.google.com/group/DataStream
我来回复
您所在位置：