“This is the 21st day of my participation in the August Text Challenge.

Follow me for more updates

Data structures and algorithms (I): time complexity and space complexity

Data structure and algorithm (two): stack

Data structures and algorithms (iii): queues

Data structures and algorithms (4): single linked lists

Data structures and algorithms (5): bidirectional linked lists

Data structures and algorithms (6): hash table

Data structures and algorithms (7): trees

Data structure and algorithm (8): sorting algorithm

Data structures and Algorithms (9): Classical algorithms interview questions

Horse board (Knight travel problem)

The checkerboard problem is an application of depth first search (DFS) for graphs.

  1. The rules of the horse-riding board game

The horse is randomly placed on a square of Board[0 ~ 7][0 ~ 7] of 8×8 chess, and the horse moves according to the rules of chess (horse moves day character). Each square is required to enter only once, covering all 64 squares on the board

  1. Solve the thought

The checkerboard problem is actually an application of depth-first search (DFS) of graphs. This can be done by backtracking (depth-first search). If the horse has reached 53 points and finds that it has reached the end of the road, it has to go back, look at other paths, and just keep backtracking on the board

  1. Solution steps and ideas

1) Create a chessBoard, which is a two-dimensional array, the value of 0 represents not gone, the value of 1 represents gone, define two arrays ArrayRow and ArrayCol, respectively represent the x and Y coordinates of the maximum 8 directions that a horse can go. Note that ArrayRow and ArrayCol should correspond one by one to meet the rules of the day the horse can go Then.

2) assume that the horse is in position (0,0), since the first horse has been laid down, define step=1 and set the current position as visited. Then start to use the for cycle to try 8 directions and determine whether the horse has not gone and not gone out of bounds.

2.1) If the judgment is yes, then step+1 and mark it as gone. If step<64 means the horse has not finished walking, then recursively put down a horse; If step=64, print the answer and return;

2.2) If not, the position of the horse should be removed and replaced, i.e. backtracked, with step-1 and checkerboard set to unvisited

Note: If you want only one answer, return at step=64. If you want all answers, you don’t have to return. Look at the location of the code marker ①

 

The complete code

#define m 6 #define n 6 int ArrayRow[]={-2 , -1 , 1 , 2 , 2 , 1 , -1 , -2}; int ArrayCol[]={-1 , -2 , -2 , -1 , 1 , 2 , 2 , 1}; int counter=0; Int Board[m][n]={0}; Void findAnswer(int x,int y,int step){int aX=0,aY=0; // for(int I =0; i<8; i++){ aX=x+ArrayRow[i]; aY=y+ArrayCol[i]; / / consider Board [aX] [aY] the if (Board (aX) [aY] = = 0 && aX && aX > < m = 0 && aY < n && aY > = 0) / / not through, and there is no cross-border {step++; Board[aX][aY]=step; If (step<m*n){findAnswer(aX,aY,step); }else{// find a solution printf(" %d\n",++counter); // add 1 printAnswer(Board); return; } step--;} step--;} step--; Board[aX][aY]=0; } } } void traverChessBoardCase() { int step=1; int x=0,y=0; // Board[x][y]=1; findAnswer(x,y,step); Void printAnswer(int Array[m][n]){int I,j; for( i=0; i<m; i++){ for(j=0; j<n; j++){ printf("%3d ",Array[i][j]); } printf("\n\n"); }}Copy the code
The output starting from (0,0) is 18 31 28 15 20 6 27 16 21 32 29 9 27 30 19 14 26 5 12 17 22 33 3 10 35 24 13 18 36 25 4 11 34 23Copy the code

If you look at the code of the checkerboard problem, you will find that it is very similar to the eight Queens problem, and you can use these two algorithms to understand the recursive algorithm

Pay attention to my

If you think MY writing is good, please click a like to pay attention to me your support is my biggest motivation!