您的位置: 首页  >  文章  >  马踏棋盘及其优化

马踏棋盘及其优化

分类: 文章 • 2025-05-05 18:34:04

马踏棋盘及其优化

问题描述：

在8*8的国际象棋棋盘中的任何一个位置，放置一个马（棋子），使其按照马在国际象棋中的规则（走日）进行移动，求其中的一个解。

问题分析：

这其实是一个深度优先搜索的问题，深度优先搜索一般使用递归实现，在这里，为了学习，使用我们更不熟悉的栈来操作。

算法:

1.给定一个起点，将起点入栈，步数step=1。
2.在map数组中的该位置的值赋为step;step++; 
3.马踏棋盘及其优化
根据上图，按照0~7的顺序试探下一个点：令direction=0,若下一个点位置合法，则下一个点入栈，再执行第3步；若下一个点位置不合法，试探下一个方向,即direction++。 4.若试探第7个方向direction==7，下一个点仍然不合法，则该点出栈，将栈顶的direction++，且将当前位置设置为栈顶的位置。 5.重复第3，4，直到步数step=64（棋盘已经被填满）或者，栈为空（没有解）（当然，一定会存在解）

代码：

#include <stdio.h>
#include <stdlib.h>

#define SIZE 8

typedef struct{

    int x;
    int y;
    int direction;
}Point;

typedef struct Node{

    Point data;
    struct Node *next;
}PathNode;

typedef struct{

    PathNode *top;
}Stack_Path;

int minindex(int p[]);//求一个数组的最小值的下标 
Stack_Path *Init_Stack(void);//初始化一个栈
void push(Stack_Path *s,Point p);//入栈
void pop(Stack_Path *s,Point *p);//出栈
int IsEmpty(Stack_Path *s);//判空
int IsQualified(Point p);//判断某一个点是否合法
void Go(int x,int y);//输入起点 
void Print();//输出路径
Point Gettop(Stack_Path *s);//获得栈顶元素 
Point NextPos(Point curpos);//生成下一个点

int map[SIZE][SIZE];//记录map[x][y]是第几步 

int main(void){

    printf("请输入起点：\n");
    int x,y;
    scanf("%d%d",&x,&y);
    Go(x,y);
    Print();
};


Stack_Path *Init_Stack(void){//使用链栈 

    Stack_Path *s=(Stack_Path *)malloc(sizeof(Stack_Path)); 
    s->top=(PathNode *)malloc(sizeof(PathNode));//头指针指向头节点 
    s->top->next=NULL;
    return s;
}

void push(Stack_Path *s,Point p){

    PathNode *newnode=(PathNode *)malloc(sizeof(PathNode));
    newnode->data=p;
    newnode->next=s->top->next;
    s->top->next=newnode;
    return ;
}
void pop(Stack_Path *s,Point *p){

    PathNode *delnode=s->top->next;
    *p=delnode->data;
    s->top->next=delnode->next;
    free(delnode);
    return ;
}

int IsEmpty(Stack_Path *s){

    if(NULL==s->top->next)
        return 1;
    else 
        return 0;
}

int IsQualified(Point p){
    //不能越界，并且，该点没有被走过 
    if(p.x>-1 && p.x<SIZE && p.y>-1 && p.y<SIZE && !map[p.x][p.y])
        return 1;
    else 
        return 0;
}
void Print(){

    for(int i=0;i<SIZE;++i){

        for(int j=0;j<SIZE;++j)
            printf("%4d",map[i][j]);
        printf("\n");
    }
}

Point Gettop(Stack_Path *s){
    //返回栈顶元素的值 
    return s->top->next->data;
}

Point NextPos(Point curpos){//返回下一个点的位置 

    int next[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
    Point nextpos;

    nextpos.x=curpos.x+next[curpos.direction][0];
    nextpos.y=curpos.y+next[curpos.direction][1];
    nextpos.direction=0;

    return nextpos;
}


void Go(int x,int y){ 

    Stack_Path *path=Init_Stack();//先创建一个栈 
    Point curpos,nextpos;//定义两个变量，一个用来存当前位置，一个用来存下一个位置 
    int step=0;//记录步数 

    //起点赋值 
    curpos.x=x; 
    curpos.y=y;
    curpos.direction=0;
    map[curpos.x][curpos.y]=++step;
    //将起点压入栈 
    push(path,curpos);

    while(step-SIZE*SIZE && !IsEmpty(path)){

        //计算处下一个点的位置 
        nextpos=NextPos(curpos);

        if(IsQualified(nextpos)){//若下一个点位置合法 

            push(path,nextpos);//压入栈 
            map[nextpos.x][nextpos.y]=++step;//地图标记 
        }
        else{//如果不合法 

            while(!IsEmpty(path) && Gettop(path).direction==7){ 
                //若栈顶元素已经试探了8次，出栈 
                pop(path,&curpos);
                --step;
                map[curpos.x][curpos.y]=0;//取消地图标记 
            }
            ++path->top->next->data.direction;//将栈顶的试探次数加一 
        }
        curpos=Gettop(path);//将当前位置设置为栈顶 
    }

    return ;
}

接下来讨论下效率问题：

最坏的情况下，每一个点都会回溯最大次数，也就是说每个点都会走8次，那么，总共走了8的64次方次，效率十分低下，主要的时间花费在了回溯上，因次，可以通过减少回溯次数来提高效率。

减少回溯次数的方法：

每次不按照顺时针的方向进行试探，优先试探可以到达的点的个数更少的点，若下一个点只有一个点可以到达，那么若行不通，一次试探后就可以回溯，这样就减少了回溯的次数。

当然，如果要求处所有的解，上述方法并不能得到优化，但是若要求出一个解，那会大大的提高效率。

代码实现：

1.首先更新数据类型

typedef struct{

    int x;
    int y;
    int direction;
    int first[8];
}Point;

这里，新加入了一个first数组，first数组用来存储方向，按照下一个可到达点的个数升序存储。顺序访问first，试探的方向就不会是顺时针，而是按照下一个点的可到达点的个数升序排列的。 direction在这里可以理解成试探的次数。

2.新加入几个函数

声明

int Getnum(Point curpos,int next[][2]);//计算一个点可以到达其他点的个数
void Setfirst(Point *curpos);//计算first数组的值
int minindex(int p[])；//找出数组最小值的下标

实现

int Getnum(Point curpos,int next[][2]){

    if(!IsQualified(curpos)) //若当前点位置不合法，没必要试探它可以到达多少个点 
        return 9; //一个点最多可以到达8个点，设置成9，为了方便后面的排序 

    int num=0;//用来记录当前点可以到达几个点 
    Point nextpos;//用来存储当前点的下一个点 
    for(int i=0;i<SIZE;++i){

        nextpos.x=curpos.x+next[i][0];
        nextpos.y=curpos.y+next[i][1];
        if(IsQualified(nextpos)) 
            num++;
    }
    if(num)
        return num;
    else //如果num==0，则说明该点没有可以到达的点，设置为9，也是为了方便排序 
        return 9;
}





void Setfirst(Point *curpos){//给first数组赋值 

    int num[8];
    //num[i]表示curpos根据next[i]到达下一个点nextpos，nextpos可以到达的点的个数 
    int next[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
    Point nextpos; 
    //先计算num数组的值 
    for(int i=0;i<8;++i){

        nextpos.x=curpos->x+next[i][0];
        nextpos.y=curpos->y+next[i][1];
        num[i]=Getnum(nextpos,next); 
    }
    //找到nextpos可到达的点最少的方向，赋值给first 
    for(int i=0;i<SIZE;++i){

        curpos->first[i]=minindex(num);
        num[minindex(num)]+=9;//最小值存过之后,加个9让它变成较大的值 
    }

    return ;
}




int minindex(int p[]){//找出一个数组中，最小值的下标 

    int min=0;
    for(int i=1;i<SIZE;++i){

        if(p[min]>p[i])
            min=i;
    }
    return min;
}

4.既然不按顺时针方向试探，就要修改NextPos()函数

Point NextPos(Point curpos){//返回下一个点的位置 

    int next[8][2]={-2,1,-1,2,1,2,2,1,2,-1,1,-2,-1,-2,-2,-1};
    Point nextpos;
            //first里存储了该点到下一个点的方向次序，derection代表试探次数 
    nextpos.x=curpos.x+next[curpos.first[curpos.direction]][0];
    nextpos.y=curpos.y+next[curpos.first[curpos.direction]][1];
    nextpos.direction=0;

    return nextpos;
}

按照冲0~7的顺序访问first数组，first数组中存储了方向

5.修改Go()函数，在压入栈之前，要给first数组赋值

void Go(int x,int y){ 

    Stack_Path *path=Init_Stack();//先创建一个栈 
    Point curpos,nextpos;//定义两个变量，一个用来存当前位置，一个用来存下一个位置 
    int step=0;//记录步数 

    //起点赋值 
    curpos.x=x; 
    curpos.y=y;
    curpos.direction=0;
    map[curpos.x][curpos.y]=++step;

    /******给first数组赋值*******/
    Setfirst(&curpos);

    //将起点压入栈 
    push(path,curpos);

    while(step-SIZE*SIZE && !IsEmpty(path)){

        //计算处下一个点的位置 
        nextpos=NextPos(curpos);

        if(IsQualified(nextpos)){//若下一个点位置合法 

            /******给first数组赋值*******/
            Setfirst(&curpos);

            push(path,nextpos);//压入栈 
            map[nextpos.x][nextpos.y]=++step;//地图标记 
        }
        else{//如果不合法 

            while(!IsEmpty(path) && Gettop(path).direction==7){ 
                //若栈顶元素已经试探了8次，出栈 
                pop(path,&curpos);
                --step;
                map[curpos.x][curpos.y]=0;//取消地图标记 
            }
            ++path->top->next->data.direction;//将栈顶的试探次数加一 
        }
        curpos=Gettop(path);//将当前位置设置为栈顶 
    }

    return ;
}

相关推荐