I need to solve a maze using backtracking method. My maze has 0 listed as a wall, 1 listed as an empty cell, 2 is for visited, 3 for dragon. Dragons are basically obstacles that I can go through BUT I need to choose the path with the LEAST dragons. So far I can solve the maze and mark a path, but I can't seem to think of a relatively simple way of finding the path with the least dragons. Do note we just started coding with C in my uni (so far I've only done java/bash/a bit of python), so I'm really new to C and algorithms in general.
Code is below.
#include <stdio.h>
#define IMPOSSIBLE (N*N+1)
int counter=0;
enum {WALL,EMPTY,VISITED,DRAGON,N};
int printMaze(int maze[N][N])
{
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
printf("%d ",maze[i][j]);
}
printf("\n");
}
}
int solveMaze(int maze[N][N], int i, int j)
{
if (maze[i][j] == WALL){ return 0; } // If [i][j] are currently a wall (0).
if (maze[i][j] == VISITED) { return 0; } // If [i][j] are currently a mark (2).
if (maze[i][j] == DRAGON) { counter++; }
maze[i][j] = VISITED; // Mark current spot with (2).
if (i==N-1 && j==N-1) { return 1; } // reached the end (N-1,N-1) - (3,3) incase N is 4.
if ( ((i < N-1) && solveMaze(maze,i+1,j)) || ((i > 0) && solveMaze(maze,i-1,j)) || ((j < N-1) && solveMaze(maze,i,j+1)) || ((j > 0) && solveMaze(maze,i,j-1)) ) { // checking index-out-bounds + recursively going around the maze
return 1;
}
maze[i][j] = EMPTY;
return 0;
}
int main() {
int maze[N][N] = { {1,1,3,3},
{3,0,1,1},
{3,0,0,1},
{1,3,3,1} };
int solved = solveMaze(maze, 0, 0);
if (solved)
{
printMaze(maze);
printf("Amount of dragons passed through in the maze: %d\n",counter);
}
else
{
printf("No solution, %d\n",IMPOSSIBLE);
}
}
I tried creating a counter that counts the amount of dragons on the way, but I guess I'm not fluent enough in recursions to make it go in every available path and choose the best one.
You seem to understand the idea of recursively traversing the tree with backtracking. The issue is that you need to find not just a path, but the one with the least cost -- that is, the fewest dragons. That means that in general, you can't stop with the first path you find. You need to keep going until you can be sure that there's no better path.
Here's one way to do it:
Maintain a variable to track the number of dragons along the best path discovered so far. Initialize it to something larger than the value that can appear along any path -- your IMPOSSIBLE
, for example, or INT_MAX
. This is separate from the number of dragons so far encountered along the path you are currently exploring.
Perform a recursive traversal much like you are already doing, except
counter
value) when you backtrack out of a dragon node.