Rat in a Maze with multiple steps or jump allowed | Maze size ; A utility function to prsolution 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 feasible solutions . ; A recursive utility function to solve Maze problem ; if ( x , y is goal ) return True ; Check if maze [ x ] [ y ] is valid ; mark x , y as part of solution path ; Move forward in x direction ; Move forward in x direction ; If moving in x direction doesn 't give  solution then Move down in y direction  ; If none of the above movements work then BACKTRACK : unmark x , y as part of solution path ; Driver Code
N = 4 NEW_LINE def printSolution ( sol ) : NEW_LINE INDENT for i in range ( N ) : NEW_LINE INDENT for j in range ( N ) : NEW_LINE INDENT print ( sol [ i ] [ 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 ] != 0 ) : NEW_LINE INDENT return True NEW_LINE DEDENT return False NEW_LINE DEDENT def solveMaze ( maze ) : NEW_LINE INDENT sol = [ [ 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 ] , [ 0 , 0 , 0 , 0 ] ] 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 ) : NEW_LINE INDENT sol [ x ] [ y ] = 1 NEW_LINE return True NEW_LINE DEDENT if ( isSafe ( maze , x , y ) == True ) : NEW_LINE INDENT sol [ x ] [ y ] = 1 NEW_LINE for i in range ( 1 , N ) : NEW_LINE INDENT if ( i <= maze [ x ] [ y ] ) : NEW_LINE INDENT if ( solveMazeUtil ( maze , x + i , y , sol ) == True ) : NEW_LINE INDENT return True NEW_LINE DEDENT if ( solveMazeUtil ( maze , x , y + i , sol ) == True ) : NEW_LINE INDENT return True NEW_LINE DEDENT DEDENT DEDENT sol [ x ] [ y ] = 0 NEW_LINE return False NEW_LINE DEDENT return False NEW_LINE DEDENT maze = [ [ 2 , 1 , 0 , 0 ] , [ 3 , 0 , 0 , 1 ] , [ 0 , 1 , 0 , 1 ] , [ 0 , 0 , 0 , 1 ] ] NEW_LINE solveMaze ( maze ) NEW_LINE