Shulou(Shulou.com)06/01 Report--

This article mainly introduces the relevant knowledge of "how to use python to solve maze problems." Xiaobian shows you the operation process through actual cases. The operation method is simple, fast and practical. I hope this article "how to use python to solve maze problems" can help you solve problems.

preface

In the maze problem, given an entrance and exit, a path is required. This article discusses three solution methods, recursive solution, backtracking solution, and queue solution.

Before describing the algorithm, consider digitizing the maze. Here, the maze is stored in a two-dimensional list (i.e., the list is nested in the list), and the unreachable positions are represented by 1, the reachable positions are represented by 0, and the positions that have been reached are represented by 2.

recursive solution

The basic idea of recursive solution is:

At each moment there is always a current position, which at the beginning is the population of the maze.

If the current location is the exit, the problem is solved.

Otherwise, if there is no way to go from the current position, the current exploration fails and steps back.

Take a feasible neighboring position and probe in the same way. If the path to the exit can be found from there, then the path to the exit from the current position is also found.

At the beginning of the whole calculation, taking the population (order pair) of the maze as the current position of the examination, the algorithm process is:

Mark the current location.

Check whether the current position is the exit, if yes, the successful end.

One by one, check whether the four neighbors of the current position can reach the exit (recursively call itself).

If the search for the neighborhood fails, report failure.

dirs=[(0, -1),(1,0),(0,-1),(-1,0)] #Offset of current position in four directions path=[] #Save the path found def mark(maze,pos): #Give the pos mark "2" to the position of the maze to mean "reversed" maze[pos[0]][pos[1]]=2 def passable(maze,pos): #Check the position pos of maze for passable return maze[pos[0]][pos[1]]==0 def find_path(maze,pos,end): mark(maze,pos) if pos==end: print(pos,end=" ") #The exit has been reached, output this position. successful conclusion path.append(pos) return True for i in range(4): #Otherwise check in four directions nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1] #Consider the next possible direction if passable(maze,nextp): #Unfeasible Neighbors Regardless of Location if find_path(maze,nextp,end):#If the exit can be reached from nextp, output this position, successfully ending print(pos,end=" ") path.append(pos) return True return False def see_path(maze,path): #Visualize the path found for i,p in enumerate(path): if i==0: maze[p[0]][p[1]] ="E" elif i==len(path)-1: maze[p[0]][p[1]]="S" else: maze[p[0]][p[1]] =3 print("\n") for r in maze: for c in r: if c==3: print('\033[0;31m'+"*"+" "+'\033[0m',end="") elif c=="S" or c=="E": print('\033[0;34m'+c+" " + '\033[0m', end="") elif c==2: print('\033[0;32m'+"#"+" "+'\033[0m',end="") elif c==1: print('\033[0;;40m'+" "*2+'\033[0m',end="") else: print(" "*2,end="") print() if __name__ == '__main__': maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\ [1,0,0,0,1,1,0,0,0,1,0,0,0,1],\ [1,0,1,0,0,0,0,1,0,1,0,1,0,1],\ [1,0,1,0,1,1,1,1,0,1,0,1,0,1],\ [1,0,1,0,0,0,0,0,0,1,1,1,0,1],\ [1,0,1,1,1,1,1,1,1,1,0,0,0,1],\ [1,0,1,0,0,0,0,0,0,0,0,1,0,1],\ [1,0,0,0,1,1,1,0,1,0,1,1,0,1],\ [1,0,1,0,1,0,1,0,1,0,1,0,0,1],\ [1,0,1,0,1,0,1,0,1,1,1,1,0,1],\ [1,0,1,0,0,0,1,0,0,1,0,0,0,1],\ [1,1,1,1,1,1,1,1,1,1,1,1,1,1]] start=(1,1) end=(10,12) find_path(maze,start,end) see_path(maze,path)

The see_path function in the code can visually print out the found path on the console, and the printed result is as follows:

S is the entry position, E is the exit position, * represents the path found, and #represents the path explored.

backtracking solution

In backtracking solutions, stacks are used primarily to store locations that can be explored. Using the feature of last-in-first-out stack, when exploring fails on a branch, it returns to the last exploitable position stored. This is a depth-first search method.

def maze_solver(maze,start,end): if start==end: print(start) return st=SStack() mark(maze,start) st.push((start,0)) #Entry and direction 0 order pair pushed into stack while not st.is_empty(): #Go back when you can't get through pos,nxt=st.pop() #Take the top of the stack and check its direction for i in range(nxt,4): #Check the unchecked directions in turn and calculate the next position nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1] if nextp==end: print_path(end,pos,st) #Arrive at exit, print position return if passable(maze,nextp): #Meet new unexplored locations st.push((pos,i+1)) #Stacking in original position and next direction mark(maze,nextp) st.push((nextp,0)) #New location pushed break #Exit the inner loop, the next iteration will continue with the new stack top as the current position print("Path not found") Queue Solver

In queue solving algorithms, queues store locations that can be explored. By using the first-in-first-out feature of the queue, we can search paths simultaneously on each branch until we find the exit. This is a breadth-first search method.

def maze_solver_queue(maze,start,end): path.append(start) if start==end: print("find path") return qu=SQueue() mark(maze,start) qu.enqueue(start) #start position enqueue while not qu.is_empty(): #And candidate positions pos=qu.dequeue() #Take the next position for i in range(4): #Check every direction nextp = pos[0] + dirs[i][0], pos[1] + dirs[i][1] if passable(maze,nextp): #Find new directions to explore if nextp==end: #is exit, success print("find path") path.append(end) return mark(maze,nextp) qu.enqueue(nextp) #new position enlist path.append(nextp) print("Path not found")

However, the queue solution method cannot directly obtain the specific path found, and other storage structures (such as linked lists) are needed to obtain the path.

The content of "how to use python to solve maze problems" is introduced here. Thank you for reading. If you want to know more about industry-related knowledge, you can pay attention to the industry information channel. Xiaobian will update different knowledge points for you every day.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.