directory
1. Maze running and backtracking algorithm
2. The role of the maze design stack
3. Python implements mazes
There are many applications of stack, this blog focuses on the stack and Backtracking algorithm combined with the design of the maze program. In fact, backtracking algorithm is also a part of artificial intelligence, usually called try and error algorithm. Most of the early computer chess games and backgammon games are based on backtracking algorithm.
1. Maze running and backtracking algorithm
Suppose a simple maze pattern looks like the following:
A maze is basically made up of four Spaces:
In the maze, you can walk up, down, left and right, as shown below:
You can take one step at a time, but if you can’t get through a wall, you have to go the other way.
Step 1: Assume the current position is at the entrance, as shown below:
Step 2: If you follow the principle of up, down, left and right, you should go up, but up is the wall, so you must go down, and then you must mark the path you have walked. In this case, it is marked in light green, so the picture on the right above is the new position in the maze, as shown below:
Step 3: Then you can find that up is the path you have traveled, so you can only go down (according to the principle of up, down, left and right, not considering the left and right are the walls). The left picture below is the new position of the maze, as shown below:
Step 4: Next, you can find that up is the path you have traveled, so you can only go down (according to the principle of up, down, left and right, not considering left and right). The picture on the bottom and right is the new position of the maze, as shown below:
Step 5: Now there are walls below, left and right, so go back to the previous path, which is the key to backtracking. Please refer to the left picture below. In this picture, the author marks the backtracking path to prevent revisiting, as shown below:
Step 6: Now the road is up and down, the left side is the wall, so go right, as shown in the picture below:
Step 7: Next up and down are the walls, and left is the path you have walked, so go right, as shown in the picture below:
Step 8: Go up because there is a road above, as shown below:
Step 9: Go up because there is a road above, as shown below:
Step 10: Since the top, left and right are all walls, go back to the previous position as shown below:
Step 11: Since the road is up and down, and the wall is on the left, go right, as shown below:
Step 12: Since the top, bottom and right are walls, go back to the previous position as shown below:
Step 13: Since the wall is on the left, go back to the previous position, as shown below:
Step 14: There is a passage below, so go down, as shown in the picture below:
Step 15: The top is where you walked, the left and bottom are the walls, so go right, as shown in the picture below:
2. The role of the maze design stack
As described above, the path traveled is marked in light green in step 2. Real programming can use stacks to store the path traveled.
The fifth step is to use the backtracking algorithm. The so-called backtracking is to walk the previous path, because the path is stored in the stack. Based on the last in, first out principle, you can pop out the previous path, which is also the focus of backtracking. When you’re done with step 4,
The maze and stack graphics are as follows:
The above maze positions use the programming language’s (row, column) flag, so to use a backtrace in step 5, pop the (3,1) coordinates from the stack and return to the (3,1) position, resulting in something like this:
3. Python implements mazes
In Python, you can design mazes using two-dimensional lists, with 0 for channels, 1 for walls, and 0 for starting and ending points.
Take the example of a maze in part 1 above, where the paths taken are represented by 2, and the paths taken that would lead to nowhere are represented by 3. In line 41 of the program, the first two parameters are the entrance of the maze, and the last two parameters are the exit of the maze. The implementation code is as follows:
# ch11_1.py from pprint import pprint maze = [# maze map [1, 1, 1, 1, 1], [1, 0, 1, 0, 1], [1, 0, 1, 0, 0, 1], [1, 0, 0, 0, 1, 1], [1, 0, 1, 0, 0, 1], [1, 1, 1, 1, 1, 1]] Directions = [# Use list to design a maze direction lambda x, y: Lambda x, y: (x+1, y), # lambda x, y: (x+1, y), # lambda x, y: (x+1, y), # lambda x, y: (x+1, y), # lambda x, y: (x+1, y), # lambda x, y: (x, y, goal_x, goal_y): Maze [x][y] = 2 stack = [] # create path stack stack. Append ((x, If (cur[0] == goal_x and cur[1] == goal_y: Print (' dir in directions ') return True # return True for dir in directions: Next = dir(cur[0], cur[1]) if maze[next[0]][next[1]] == 0: Append (next) maze[next[0]][next[1]] = 2 Maze [cur[0]][cur[1]] = 3 # Mark dead stack.pop() # Trace else: Print (" No path ") return False maze_solve(1, 1, 4, 4) pprint(maze) # skip the display elementCopy the codeThe running effect is as follows:
Project source download: stack, backtracking algorithm to design maze procedures
Source: Tsinghua Computer School