Optimizing this maze-solver I've written C# code for solving a maze problem.  It works, but I want to optimize it so that it could give me all paths.  To solve the maze, I walk on the zeros and assumed that the final is reaching -3.     

const int MAZE_SIZE = 6;
static int[] allowed_move_row = { 0, -1, 0, 1 };
static int[] allowed_move_col = { 1, 0, -1, 0 };
const int MAX_ALLOWED_MOVES = 4;
static int[,] Optmaze = new int[MAZE_SIZE, MAZE_SIZE];
static int[,] maze  = new int[MAZE_SIZE, MAZE_SIZE] { 
                       { -2 , 0  ,  0   , 0  ,  0  ,  -1 },
                       { -1 , 0  , -1   , 0  , -1  ,  0 } ,
                       { -1 , -1 , -1   , 0  ,  0  ,  0 } ,
                       { -1 , 0  , -1   , -1 ,  0  ,  -1 },
                       { -1 , -1 , -1   , 0  ,  0  ,  0 } ,
                       { -1 , 0  , -1   , -3 ,  0  ,  0 } };

static bool Solve(int previous_row, int previous_col, int next_step_no)
{
     for (int i = 0; i &lt; MAX_ALLOWED_MOVES; i++)
     {
          int col = previous_col + allowed_move_col[i];
          int row = previous_row + allowed_move_row[i];
          if (col &lt; 0 || col &gt;= MAZE_SIZE) 
              continue;
          if (row &lt; 0 || row &gt;= MAZE_SIZE) 
              continue;

          if (maze[row, col] == -3)
              return true;

          if (maze[row, col] != 0) 
              continue;

          maze[row, col] = next_step_no;

          if (Solve(row, col, next_step_no + 1))
              return true;

          else maze[row, col] = 0;
     }
            return false;
}

static void Main(string[] args)
{
    Print(maze);
    Console.WriteLine("-----------Solve-------------");
    if (Solve (0, 0, 1) )
        Print( maze);
    else
        Console.WriteLine("No Result");
}

static void Print(int[,] maze)
{
    for (int i = 0; i &lt; maze.GetLength(0); i++)
    {
        for (int j = 0; j &lt; maze.GetLength(1); j++)
        {
            Console.Write(" " + String.Format("{0,3}",maze[i, j]) + " ");
        }
        Console.WriteLine();
    }
}


Outputting:


       -2    0    0    0    0   -1
       -1    0   -1    0   -1    0
       -1   -1   -1    0    0    0
       -1    0   -1   -1    0   -1
       -1   -1   -1    0    0    0
       -1    0   -1   -3    0    0
       -----------Solve-------------
       -2    1    2    3    0   -1
       -1    0   -1    4   -1    0
       -1   -1   -1    5    6    0
       -1    0   -1   -1    7   -1
       -1   -1   -1    0    8    9
       -1    0   -1   -3   11   10
Walking all zeros is indeed suboptimal. A good first optimization is to preferentially walk on the zeros that bring you closer to the end point.

To do this, at each step calculate the pythagorean distance between the x,y coords of the array entry you're considering walking to, and the x,y coords of the array entry containing -3. This will be the cost of walking to that square. Store all calculated costs so you don't have to recalculate them.

Then, continue to preferentially choose lowest-cost next squares until you reach the end or a dead end. In cases of dead ends, simply go back and choose the next lowest-cost square that has yet to be traversed. To do this, you will need to keep some notion of path hierarchy, i.e. which steps lead to which next potential steps. A custom node type will do this for you.

If you've made it this far, then congratulations! You have a rudimentary A* path-finding algorithm. For a helpful guide to implementing this algorithm I recommend this resource.

There are further enhancements to A* efficiency, such as the Jump Point Search algorithm, which is best for more open spaces.