title: Number of solutions for rat in a maze puzzle
body: <p>Rat in Maze Puzzle - A Maze is given as N*N binary matrix of blocks where source block is the upper left most block i.e., maze[0][0] and destination block is lower rightmost block i.e., maze[N-1][N-1]. A rat starts from source and has to reach destination. The rat can move any directions: forward,down,Left,Right.In the maze matrix, 0 means the block is dead end and 1 means the block can be used in the path from source to destination.
  <a href="https://i.stack.imgur.com/ZBONp.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ZBONp.png" alt="enter image description here"></a></p>
  
  <p>Problem - Find all possible solutions and the number of solutions to get the rat out of the maze.
  I was able to find a "single solution" for rat in a maze puzzle. But how do i determine different possible solutions and the number of solutions? Pasting the code below which will determine a single solution and prints the same. Please help me how do i determine different possible solution and the number of solutions as well.</p>
  
  <pre><code>#include&lt;stdio.h&gt;
  #include&lt;conio.h&gt;
  #define N 5 //Maze Size 5X5 matrix
  
  //Function declarations
  void maze(int m[N][N]);
  int maze_soln(int soln[N][N], int m[N][N],int ,int,int path[N][N]);
  int issafe(int m[N][N], int x, int y,int path[N][N]);
  
  // This function checks for valid cell. If already visited in the past
  // path[][] will take care of returning false.
  int issafe(int m[N][N], int x, int y,int path[N][N])
  {
      if (x &gt;= 0 &amp;&amp; y &gt;= 0 &amp;&amp; x &lt; N &amp;&amp; y &lt; N &amp;&amp; m[x][y] == 1 &amp;&amp; path[x][y] !=1)
          return true; // Valid cell.
      else
          return false;
  }
  
  // Maze solutions. Checks for proper cell. finds proper path 
  // By going LEFT,RIGHT,UP or DOWN
  int maze_soln(int soln[N][N], int m[N][N],int x,int y,int path[N][N])
  {
      //All the cells have been visited
      if (x == N - 1 &amp;&amp; y == N - 1)
      {
          soln[x][y] = 1; //mark the cell as possible path
          return true;
      }
  
      // Find out different paths
      if (issafe(m, x, y,path) == true)
      {
          soln[x][y] = 1; // mark the cell as possible solution
          path[x][y] = 1; //mark the path as visited
  
          // Go RIGHT and see if there's a path
          if (maze_soln(soln, m, x, y + 1,path))
              return true;
  
          //LEFT
          if (y&gt; 0 &amp;&amp; maze_soln(soln, m, x, y-1,path))
              return true;
  
          //DOWN
          if (maze_soln(soln, m, x + 1, y,path))
              return true;
  
          //UP
          if (x&gt;0 &amp;&amp; maze_soln(soln, m, x - 1, y,path))
              return true;
  
          soln[x][y] = 0;
          return false;
      }
      return false;
  }
  
  // Prints the solution matrix if proper path is found
  void maze(int m[N][N])
  {
      int i, j;
      int soln[N][N] = { 0 };
      int path[N][N] = { 0 };
      if (maze_soln(soln, m, 0, 0,path) == true)
      {
          printf("\n Solution\n"); //Print solution matrix
          for (i = 0; i &lt; N; i++)
          {
              for (j = 0; j &lt; N; j++)
              {
                  printf("\t%d", soln[i][j]);
              }
              printf("\n");
          }
      }
  
      return;
  }
  
  // Main function
  int main()
  {
      int i, j;
      //Maze matrix
      int m[N][N] = { { 1,1,1,0,0 },
                      { 1,1,0,1,0 },
                      { 0,1,0,1,1 },
                      { 1,1,1,1,1 },
                      { 1,0,0,1,1 } };
  
      //Print the Maze
      printf("MAZE\n");
      for (i = 0; i &lt; N; i++)
      {
          for (j = 0; j &lt; N; j++)
          {
              printf("\t%d", m[i][j]);
          }
          printf("\n");
      }
  
      //Call maze function to find out the path
      // and print the solution matrix
      maze(m);
      _getch();
  }
  </code></pre>