# 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 < MAX_ALLOWED_MOVES; i++)
{
int col = previous_col + allowed_move_col[i];
int row = previous_row + allowed_move_row[i];
if (col < 0 || col >= MAZE_SIZE)
continue;
if (row < 0 || row >= 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 < maze.GetLength(0); i++)
{
for (int j = 0; j < 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

• I would parallelize the algorithm to make it search from both ends of the maze and stop when they meet half way. More of a brute force optimization than anything cleaver. – Admiral Nelson Nov 8 '13 at 18:20
• You need to fully define "all paths." I could loop around the same two positions a few billion times and then get back on a path that actually finds a solution and this would be a "path." – Austin Salonen Nov 8 '13 at 18:24
• You can use pathing or search algorithms for this such as A*, B* etc. See wikipedia's the side bar for different approaches to solve pathing problems like this one. – John S. Nov 8 '13 at 18:32
• A helpful answer could be: stackoverflow.com/a/1523678/1445661 – mao47 Nov 8 '13 at 18:37