Algorithm of horse stepping on chessboard

Algorithm of horse stepping on chessboard

Definition: the horse is randomly placed in a square of the Board[0-7] [0-7] of the 8 × 8 chess board, and moves according to the rules of walking chess. Each square is required to enter only once and walk through all 64 squares on the chessboard.

Algorithm: as shown in the figure:

A two-dimensional array is used to store the chessboard. If the coordinate of the horse is (x, y), then there are eight possibilities for the next position to be selected. All we have to do is start from position 0, and judge whether the new horse position is available in turn. If it is not available (that is, the horse has already passed the position), we will traverse the next possible position 1 until position 7 stops. If there is no available position, we will carry out backtracking. If we trace back to the starting position, it means that the road is blocked, that is, we cannot traverse from this position The whole chessboard. If the available position is found in the process of traversing position 0-7, the position coordinate is given to (x, y). Then, recursion is used to find the new jumping position of the horse again. Until the horse jumps 64 times, it stops. At this time, the horse has passed the whole chessboard.

Operation result: each inspection may be different

#include<stdio.h>
#include<time.h>

#define X 8
#define Y 8

int chess[X][Y];
//Find the next walkable position based on (x,y) position
int nextxy(int *x,int *y,int count)
{
    switch(count)
    {
   case 0:
    if(*x+2<=X-1&&*y-1>=0&&chess[*x+2][*y-1]==0)//1 on the right 2 y of x has not been traversed
    {
        *x+=2;
        *y-=1;
        return 1;
    }
    break;
    case 1:
    if(*x+2<=X-1&&*y+1<=Y-1&&chess[*x+2][*y+1]==0)//2 y to the right of x, 1 has not been traversed
    {
        *x+=2;
        *y+=1;
        return 1;
    }
    break;
    case 2:
    if(*x-2>=0&&*y-1>=0&&chess[*x-2][*y-1]==0)//1 on x left 2 y has not been traversed
    {
        *x-=2;
        *y-=1;
        return 1;
    }
    break;
    case 3:
    if(*x-2>=0&&*y+1<=Y-1&&chess[*x-2][*y+1]==0)//x left 2 y down 1 not traversed
    {
        *x-=2;
        *y+=1;
        return 1;
    }
    break;
     case 4:
    if(*x+1<=X-1&&*y-2>=0&&chess[*x+1][*y-2]==0)//2 on the right 1 y of x has not been traversed
    {
        *x+=1;
        *y-=2;
        return 1;
    }
    break;
     case 5:
    if(*x+1<=X-1&&*y+2<=Y-1&&chess[*x+1][*y+2]==0)//x right 1 y down 2 not traversed
    {
        *x+=1;
        *y+=2;
        return 1;
    }
    break;
     case 6:
    if(*x-1>=0&&*y-2>=0&&chess[*x-1][*y-2]==0)//x left 1 y up 2 not traversed
    {
        *x-=1;
        *y-=2;
        return 1;
    }
    break;
     case 7:
    if(*x-1>=0&&*y+2<=Y-1&&chess[*x-1][*y+2]==0)//x left 1 y down 2 not traversed
    {
        *x-=1;
        *y+=2;
        return 1;
    }
    break;
     default:
        break;
    }
    return 0;
}
void print()
{
    int i,j;
    for(i=0;i<X;i++)
    {
        for(j=0;j<Y;j++)
        {
           printf("%2d\t",chess[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
//The depth first traversal chessboard (x,y) is the position coordinate tag is the marker variable, each step, tag+1
/*Method 1
//int traverse(int x,int y,int count)
{
    int x1=x,y1=y; //New node location
    if(count>X*Y) //If it is all traversed and available, it will return.
        return 1;
    int flag,result,i;
    for(i=0;i<8;i++)
    {
        flag=nextxy(&x1,&y1,i); //Find the next available location
        if(1==flag)
        {
            chess[x1][y1]=count; //The newly found node ID is available,
            result=traverse(x1,y1,count+1); //Recurse the next available node again based on the new node
            if(result) //The current chessboard is available
            {
                return 1;
            }
            else //The newly found node has no next available location for backtracking
            {
                chess[x1][y1]=0;
                x1=x; //The node location should also be traced back
                y1=y;
            }
        }
    }
    return 0;
}*/
//Method two
int Travelchessboard(int x,int y,int tag)
{
    int x1=x,y1=y,flag=0,count =0;
    chess[x][y]=tag;

    if(X*Y==tag)
    {
       //Print chessboard
        return 1;
    }
    //Find the next walking coordinate (x1,y1) of the horse. If flag=1 is found, otherwise flag=0
    flag=nextxy(&x1,&y1,count);

    while(flag==0&&count<7)//It can't be judged that the function above returns 0, that is to say, eight ways to go with flag = 0
    {
        count++;//No, I can't. I have to come out
        flag=nextxy(&x1,&y1,count);
    }
    while(flag)
    {
        if(Travelchessboard(x1,y1,tag+1))
        {
            return 1;
        }
        //Continue to find the next walking coordinate (x1,y1) of the horse. If flag=1 is found, otherwise flag=0
        x1=x;
        y1=y;
        count++;

        flag=nextxy(&x1,&y1,count);
        while(flag==0&&count<7)//It can't be judged that the function above returns 0, that is, flag=0
        {
        count++;
        flag=nextxy(&x1,&y1,count);
        }
    }
    if(0==flag)
    {
        chess[x][y]=0;//Return to 0 to search again
    }
    return 0;
}
int main()
{
    int i,j;
    clock_t start,finish;

    start=clock();

    for(i=0;i<X;i++)
    {
        for(j=0;j<Y;j++)
        {
            chess[i][j]=0;
        }
    }
    if(!Travelchessboard(2,0,1))
    {
       printf("Sorry, chessboard traversal failed");
    }
    print();
    finish=clock();
    printf("This calculation takes a total of time:%f second\n\n",(double)(finish-start)/CLOCKS_PER_SEC);
    return 0;
}

 

Posted on Fri, 31 Jan 2020 11:09:03 -0800 by Gighalen