python - 当我尝试运行 maze_solver 代码时我没有得到输出，我如何获得预期的输出？

Question

N = 4

def printSolution( sol ): 
    
    for i in sol: 
        for j in i: 
            print(str(j) + " ", end ="") 
        print("") 


def isSafe( maze, x, y, visited): 
    
    if x >= 0 and x < N and y >= 0 and y < N and maze[x][y] == 1 and visited[x][y] == True: 
        return True
    
    return False


def solveMaze( maze ): 
    
    sol = [ [ 0 for j in range(4) ] for i in range(4) ] 
    visited = [ [ 0 for j in range(4) ] for i in range(4) ]
    
    if solveMazeUtil(maze, 0, 0, sol, visited) == False: 
        print("Solution doesn't exist")
        print(-1)
        return False
    
    printSolution(sol) 
    return True
    
def solveMazeUtil(maze, x, y, sol, visited): 
    if x == N - 1 and y == N - 1 and maze[x][y]== 1: 
        sol[x][y] = 1
        return True
        
    
    if isSafe(maze, x, y, visited) == True:
        sol[x][y] = 1
        if solveMazeUtil(maze, x + 1, y, sol, visited) == True:
            visited[x][y] = True 
            return True
        if solveMazeUtil(maze, x - 1, y, sol, visited) == True:
            visited[x][y] = True
            return True
                
        if solveMazeUtil(maze, x, y - 1, sol, visited) == True:
            visited[x][y] = True
            return True
        if solveMazeUtil(maze, x, y + 1, sol, visited) == True: 
            visited[x][y] = True
            return True
        
        
        

        sol[x][y] = 0
        return False

    
if __name__ == "__main__": 
    
    maze = [ [1, 0, 0, 0], 
            [1, 1, 0, 1], 
            [0, 1, 0, 0], 
            [1, 1, 1, 0] ] 
            
    solveMaze(maze)

标签： python

Answer 1

对您的代码进行以下细微更改即可使其正常工作。

在代码中添加注释以突出显示更改。

代码

# N = 4 -- removed (get dimension of maze using len function) 

def printSolution( sol ): 
    
    for i in sol: 
        for j in i: 
            print(str(j) + " ", end ="") 
        print("") 

def isSafe( maze, x, y, visited): 
    N = len(maze)      # Get Maze dimensions (N x M) rather than hardcoding using N as a global
    M = len(maze[0])
    
    # x, y safe to use if not visited (original code had visited)
    #if x >= 0 and x < N and y >= 0 and y < N and maze[x][y] == 1 and visited[x][y] == True: 
    # Can simplify x >= 0 and x < N to 0 <= x < M
    return 0 <= x < N and 0 <= y < M and maze[x][y] == 1 and not visited[x][y]

def solveMaze( maze ): 
    N = len(maze)      # Get Maze dimensions (N x M) rather than hardcoding using N as a global
    M = len(maze[0])
    sol = [ [ 0 for j in range(M) ] for i in range(N) ] 
    visited = [ [ 0 for j in range(M) ] for i in range(N) ]
    
    if not solveMazeUtil(maze, 0, 0, sol, visited): # preferred to checking for False
        print("Solution doesn't exist")
        print(-1)
        return False
    
    printSolution(sol) 
    return True
    
def solveMazeUtil(maze, x, y, sol, visited): 
    N = len(maze)      # Get Maze dimensions (N x M) rather than hardcoding using N as a global
    M = len(maze[0])
    
    if x == N - 1 and y == M - 1 and maze[x][y]== 1: 
        sol[x][y] = 1
        return True
        
    if isSafe(maze, x, y, visited): # preferred to checking for True
        sol[x][y] = 1         # Try solution from current x, y position
        visited[x][y] = True  # Mark as visited so no other soltuion will use it
        
        # Recursive calls to solveMazeUtil can be simplfied to the following:
        if (solveMazeUtil(maze, x + 1, y, sol, visited) or 
            solveMazeUtil(maze, x - 1, y, sol, visited) or 
            solveMazeUtil(maze, x, y - 1, sol, visited) or 
            solveMazeUtil(maze, x, y + 1, sol, visited)):
            return True   # Found a solution
        else:
            sol[x][y] = 0 # Couln't use x, y in solution
        return False
    else:
        return False

if __name__ == "__main__": 
    print("Test 1")
    maze = [ [1, 0, 0, 0], 
            [1, 1, 0, 1], 
            [0, 1, 0, 0], 
            [1, 1, 1, 0] ] 
    solveMaze(maze)
    
    print("\nTest 2")
    maze = [ [1, 0, 0, 0], 
            [1, 1, 0, 1], 
            [0, 1, 0, 0], 
            [1, 1, 1, 1] ] 
    solveMaze(maze)
    
    print("\nTest 3")
    maze = [ [1, 0, 0, 0], 
            [1, 1, 0, 1], 
            [0, 1, 0, 0], 
            [1, 1, 0, 1],
            [1, 1, 1, 1]] 
    solveMaze(maze)

输出

Test 1
Solution doesn't exist
-1

Test 2
1 0 0 0 
1 1 0 0 
0 1 0 0 
0 1 1 1 

Test 3
1 0 0 0 
1 1 0 0 
0 1 0 0 
0 1 0 0 
0 1 1 1 

面向对象版本

class Maze:
  def __init__(self, maze):
    # Constructor
    self.maze = maze

  def size(self):
    # Tuple for Maze dimensions
    return len(self.maze), len(self.maze[0])

  def isSafe(self, x, y, visited):
    '''
      Checks if okay to select cell x, y
    '''
    # Get Maze dimensions (N x M)
    N, M = self.size()

    # x, y safe to use if not visited (original code had visited)
    #if x >= 0 and x < N and y >= 0 and y < N and maze[x][y] == 1 and visited[x][y] == True: 
    # Can simplify x >= 0 and x < N to 0 <= x < M
    return 0 <= x < N and 0 <= y < M and self.maze[x][y] == 1 and not visited[x][y]

  def solveMaze(self):
    '''
       Controlling function for Maze solver
    ''' 
    # Get Maze dimensions (N x M)
    N, M = self.size()

    sol = [ [ 0 for j in range(M) ] for i in range(N) ] 
    visited = [ [ 0 for j in range(M) ] for i in range(N) ]
    
    if not self.solveMazeUtil(0, 0, sol, visited): # preferred to checking for False
      print("Solution doesn't exist")
      print(-1)
      return False
    
    self.printSolution(sol) 
    return True

  def solveMazeUtil(self, x, y, sol, visited): 
    '''
      Recursive Maze solver
    '''
    # Get Maze dimensions (N x M)
    N, M = self.size()
    
    if x == N - 1 and y == M - 1 and self.maze[x][y]== 1: 
        sol[x][y] = 1
        return True
        
    if self.isSafe(x, y, visited): # preferred to checking for True
        sol[x][y] = 1         # Try solution from current x, y position
        visited[x][y] = True  # Mark as visited so no other soltuion will use it
        
        # Recursive calls to solveMazeUtil can be simplfied to the following:
        if (self.solveMazeUtil(x + 1, y, sol, visited) or 
            self.solveMazeUtil(x - 1, y, sol, visited) or 
            self.solveMazeUtil(x, y - 1, sol, visited) or 
            self.solveMazeUtil(x, y + 1, sol, visited)):
            return True   # Found a solution
        else:
            sol[x][y] = 0 # Couln't use x, y in solution
        return False
    else:
        return False

  def printSolution(self, sol ): 
    '''
      Format and print solution
    '''
    for i in sol: 
      for j in i: 
          print(str(j) + " ", end ="") 
      print("") 

if __name__ == "__main__": 
    print("Test 1")
    maze = Maze([ [1, 0, 0, 0], 
            [1, 1, 0, 1], 
            [0, 1, 0, 0], 
            [1, 1, 1, 0] ])

    maze.solveMaze() 
    
    print("\nTest 2")
    maze = Maze([ [1, 0, 0, 0], 
            [1, 1, 0, 1], 
            [0, 1, 0, 0], 
            [1, 1, 1, 1] ])
    maze.solveMaze() 
    
    print("\nTest 3")
    maze = Maze([ [1, 0, 0, 0], 
            [1, 1, 0, 1], 
            [0, 1, 0, 0], 
            [1, 1, 0, 1],
            [1, 1, 1, 1]])
    maze.solveMaze() 

输出

与非 OO 版本相同