Rat in a Maze | Backtracking | Maze size ; A utility function to print solution matrix sol ; A utility function to check if x , y is valid index for N * N Maze ; if ( x , y outside maze ) return false ; This function solves the Maze problem using Backtracking . It mainly uses solveMazeUtil ( ) to solve the problem . It returns false if no path is possible , otherwise return true and prints the path in the form of 1 s . Please note that there may be more than one solutions , this function prints one of the feasable solutions . ; A recursive utility function to solve Maze problem ; if ( x , y is goal ) return True ; Check if maze [ x ] [ y ] is valid ; Check if the current block is already part of solution path . ; mark x , y as part of solution path ; Move forward in x direction ; If moving in x direction doesn 't give solution  then Move down in y direction ; If moving in y direction doesn 't give solution then  Move back in x direction ; If moving in backwards in x direction doesn 't give solution  then Move upwards in y direction ; If none of the above movements work then BACKTRACK : unmark x , y as part of solution path ; Driver program to test above function
N = 4 NEW_LINE def printSolution ( sol ) : NEW_LINE INDENT for i in sol : NEW_LINE INDENT for j in i : NEW_LINE INDENT print ( str ( j ) + " ▁ " , end = " " ) NEW_LINE DEDENT print ( " " ) NEW_LINE DEDENT DEDENT def isSafe ( maze , x , y ) : NEW_LINE INDENT if x >= 0 and x < N and y >= 0 and y < N and maze [ x ] [ y ] == 1 : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def solveMaze ( maze ) : NEW_LINE INDENT sol = [ [ 0 for j in range ( 4 ) ] for i in range ( 4 ) ] NEW_LINE if solveMazeUtil ( maze , 0 , 0 , sol ) == False : NEW_LINE INDENT print ( " Solution ▁ doesn ' t ▁ exist " ) ; NEW_LINE return False NEW_LINE DEDENT printSolution ( sol ) NEW_LINE return True NEW_LINE DEDENT def solveMazeUtil ( maze , x , y , sol ) : NEW_LINE INDENT if x == N - 1 and y == N - 1 and maze [ x ] [ y ] == 1 : NEW_LINE INDENT sol [ x ] [ y ] = 1 NEW_LINE return True NEW_LINE DEDENT if isSafe ( maze , x , y ) == True : NEW_LINE INDENT if sol [ x ] [ y ] == 1 : NEW_LINE INDENT return False NEW_LINE DEDENT sol [ x ] [ y ] = 1 NEW_LINE if solveMazeUtil ( maze , x + 1 , y , sol ) == True : NEW_LINE INDENT return True NEW_LINE DEDENT if solveMazeUtil ( maze , x , y + 1 , sol ) == True : NEW_LINE INDENT return True NEW_LINE DEDENT if solveMazeUtil ( maze , x - 1 , y , sol ) == True : NEW_LINE INDENT return True NEW_LINE DEDENT if solveMazeUtil ( maze , x , y - 1 , sol ) == True : NEW_LINE INDENT return True NEW_LINE DEDENT sol [ x ] [ y ] = 0 NEW_LINE return False NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT maze = [ [ 1 , 0 , 0 , 0 ] , [ 1 , 1 , 0 , 1 ] , [ 0 , 1 , 0 , 0 ] , [ 1 , 1 , 1 , 1 ] ] NEW_LINE solveMaze ( maze ) NEW_LINE DEDENT