Rat in a Maze | Backtracking | C # program to solve Rat in a Maze problem using backtracking ; Size of the maze ; A utility function to print solution matrix sol [ N , N ] ; 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 ; 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 doesm 't give  solution then Move backward 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 works then BACKTRACK : unmark x , y as part of solution path ; Driver Code
using System ; class RatMaze { static int N ; void printSolution ( int [ , ] sol ) { for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < N ; j ++ ) Console . Write ( " ▁ " + sol [ i , j ] + " ▁ " ) ; Console . WriteLine ( ) ; } } bool isSafe ( int [ , ] maze , int x , int y ) { return ( x >= 0 && x < N && y >= 0 && y < N && maze [ x , y ] == 1 ) ; } bool solveMaze ( int [ , ] maze ) { int [ , ] sol = new int [ N , N ] ; if ( solveMazeUtil ( maze , 0 , 0 , sol ) == false ) { Console . Write ( " Solution ▁ doesn ' t ▁ exist " ) ; return false ; } printSolution ( sol ) ; return true ; } bool solveMazeUtil ( int [ , ] maze , int x , int y , int [ , ] sol ) { if ( x == N - 1 && y == N - 1 && maze [ x , y ] == 1 ) { sol [ x , y ] = 1 ; return true ; } if ( isSafe ( maze , x , y ) == true ) { if ( sol [ x , y ] == 1 ) return false ; sol [ x , y ] = 1 ; if ( solveMazeUtil ( maze , x + 1 , y , sol ) ) return true ; if ( solveMazeUtil ( maze , x , y + 1 , sol ) ) return true ; if ( solveMazeUtil ( maze , x - 1 , y , sol ) ) return true ; if ( solveMazeUtil ( maze , x , y - 1 , sol ) ) return true ; sol [ x , y ] = 0 ; return false ; } return false ; } public static void Main ( String [ ] args ) { RatMaze rat = new RatMaze ( ) ; int [ , ] maze = { { 1 , 0 , 0 , 0 } , { 1 , 1 , 0 , 1 } , { 0 , 1 , 0 , 0 } , { 1 , 1 , 1 , 1 } } ; N = maze . GetLength ( 0 ) ; rat . solveMaze ( maze ) ; } }