Backtracking

Backtracking is a method to solve problems using recursion, by trying to find different solutions by erasing or forgetting about a solution if it turns out to be invalid.

I’m pretty sure this is just DFS.

It is especially relevant as an introductory pathfinding (and maze-solving) algorithm.

Mazes

The idea is we start at a grid position, then to make a move we check if all four directions give us a valid path. We can leave markers behind us to show that we’ve been at that position already.¹

// assume char maze[4][4] is global, initialised
// that we stored height and width
bool solveMaze(int i, int j) { // returns false if invalid step to exit, true otherwise
	if (i < 0 || i >= height || j < 0 || j >= width) // bounds checking
		return false;
	if (maze[i][j] == 'E') // reached the exit
		return true;
	if (maze[i][j] != ' ') // found a wall or checked step
		return false;
	maze[i][j] = '*'; // a potential path
	if (solveMaze(i + 1, j)) // look down
		return true; // if true, then current location is true
	if (solveMaze(i - 1, j)) // look up
		return true;
	if (solveMaze(i, j + 1)) // look right
		return true;
	if (solveMaze(i, j - 1)) // look left
		return true;
	// if we've gotten here then not a potential path
	maze[i][j] = ' ';
	return false;
}

Footnotes

1. From Prof Emara’s lecture notes. ↩