Maze Solving Algorithm in C++

To have a chance in solving it, you must:

• Create a Solve() routine and recursively call itself:
  • if 1st, 2nd, 3rd, ... are true Solve has succeeded in finding a solution
  • if 1st, 2nd, 3rd, ... contains a false, it has to backtrack and find another way
• You need to build a buffer of places you've been to avoid infinite loops
  • as you make moves it needs to keep tabs on it
  • when we hit a dead end, we need to erase bad moves
  • we can implement the above by burning in a guess and removing it if it's wrong

Here's a crude implementation based on the above concepts:

#include <stdio.h>

const int mazeRows = 9;
const int mazeColumns = 9;
char maze[mazeRows][mazeColumns + 1] = {
    "# #######",
    "#   #   #",
    "# ### # #",
    "# #   # #",
    "# # # ###",
    "#   # # #",
    "# ### # #",
    "#   #   #",
    "####### #",
};
const char wall = '#';
const char free = ' ';
const char someDude = '*';

class COORD
{
public:
    int x;
    int y;
    COORD(int _x = 0, int _y = 0) { x = _x, y = _y; }
    COORD(const COORD &coord) { x = coord.x; y = coord.y; }
};
COORD startingPoint(1, 0);
COORD endingPoint(7, 8);

void printDaMaze() {
    for (int Y = 0; Y < mazeRows; Y++) {
        printf("%s\n", maze[Y]);
    }
    printf("\n");
}

char get(int x, int y) {
    if (x < 0 || x >= mazeColumns || y < 0 || y >= mazeRows) return wall;
    return maze[y][x];
}

void set(int x, int y, char ch) {
    if (x < 0 || x >= mazeColumns || y < 0 || y >= mazeRows) return;
    maze[y][x] = ch;
}

bool solve(int x, int y) {
    // Make the move (if it's wrong, we will backtrack later. To illustrate, I have a version of the below in Javascript)
    set(x, y, someDude);

    // If you want progressive update, uncomment these lines...
    //printDaMaze();
    //sleep(50);
    // Check if we have reached our goal.
    if (x == endingPoint.x && y == endingPoint.y) return true;
    // Recursively search for our goal.
    if (get(x - 1, y) == free && solve(x - 1, y)) return true;
    if (get(x + 1, y) == free && solve(x + 1, y)) return true;
    if (get(x, y - 1) == free && solve(x, y - 1)) return true;
    if (get(x, y + 1) == free && solve(x, y + 1)) return true;
    // Otherwise we need to backtrack and find another solution.
    set(x, y, free);
    // If you want progressive update, uncomment these lines...
    //printDaMaze();
    //sleep(50);
    return false;
}

int main(int argc, char* argv[]) {
    if (solve(startingPoint.x, startingPoint.y)) {
        printDaMaze();
        printf("Solved!\n");
    } else {
        printf("Cannot solve. :-(\n");
    }
    return 0;
}

To illustrate, I have a version of the above running in JavaScript:

const mazeColumns = 9;
const mazeRows = 9;

let maze = [
    "# #######",
    "#   #   #",
    "# ### # #",
    "# #   # #",
    "# # # ###",
    "#   # # #",
    "# ### # #",
    "#   #   #",
    "####### #"
].map(line => line.split(''));
const wall = '#';
const free = ' ';
const someDude = '*';
const startingPoint = [1, 0];
const endingPoint = [7, 8];

function printDaMaze() {
    //maze.forEach(line => console.log(line.join('')))
    let txt = maze.reduce((p, c) => p += c.join('') + '\n', '')
    let html = txt.replace(/[*]/g, c => '<font color=red>*</font>')
    $('#mazeOutput').html(html);
}

function get(x, y) {
    if (x < 0 || x >= mazeColumns || y < 0 || y >= mazeRows) return wall;
    return maze[y][x];
}

function set(x, y, ch) {
    if (x < 0 || x >= mazeColumns || y < 0 || y >= mazeRows) return;
    maze[y][x] = ch;
}

async function solve(x, y) {
    // Make the move (if it's wrong, we will backtrack later.
    set(x, y, someDude);
    printDaMaze();
    await sleep(100);
    // Check if we have reached our goal.
    if (x === endingPoint[0] && y === endingPoint[1]) return true
    // Recursively search for our goal.
    if (get(x - 1, y) === free && await solve(x - 1, y)) return true;
    if (get(x + 1, y) === free && await solve(x + 1, y)) return true;
    if (get(x, y - 1) === free && await solve(x, y - 1)) return true;
    if (get(x, y + 1) === free && await solve(x, y + 1)) return true;
    // Otherwise we need to backtrack and find another solution.
    set(x, y, free);
    printDaMaze();
    await sleep(100);
    return false;
}

function sleep(ms) {
    return new Promise((resolve) => setTimeout(resolve, ms));
}

(async function() {
    if (await solve(startingPoint[0], startingPoint[1])) {
        console.log("Solved!");
    } else {
        console.log("Cannot solve. :-(");
    }
})();

<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script>
<pre id="mazeOutput">
</pre>

As Luchian already posted, the algorithm (even if implemented correctly) is not suitable to find your way out of all sort of mazes: If you have some loop inside your maze, you might just end up running around this looping wall.

Also, as it seems, you don't really generate a maze but rather a big field with walls at the borders and the "exit" somewhere inside it. An algorithm, which really "sticks to a wall" will never find the exit, if the exit is not near the wall (which, again, is currently only at the borders of your "maze").

Since you're not removing the SomeDudes, i.e. the positions you've already been, and you're treating SomeDude the same way as a Wall, you're slowly filling up the maze with some kind of "SomeDude-Wall": You go just down until you hit the border and then go in big counterclockwise spirals around the field, leaving a trace of SomeDudes.

Depending on your starting point and the exit, you can easily run into the situation, where all four directions are blocked, either by a "real" wall or by some previous SomeDude you left there. Then, none of the four if-Statements is executed and you just have an infinite loop (since nothing is changed inside the loop body).

For an algorithm, wich sticks to a wall (and thus would be able to find a way out of some kinds of mazes), I would suggest the following steps:

• First, go into one direction, until you hit a wall.
• Set your current direction, so that the wall is at your right side.
• Follow your current direction (don't forget to delete your SomeDude-trace) until either
  • You've found the exit.
  • There is no wall at your right side: In this case, turn right and go one step forward.
  • Or, there is a wall just in front of you. In this case, turn left until the way ahead of you is free

This way, you ensure, that there is always "the same" wall at your right side, so you "stick" to that wall.

Remember, that this algorithm cannot find exits, if the exit is inside some free space (since it always stick to a wall, the exit must also be near a wall to be found).

For an algorithm which finds its way out of all possible mazes, you need to have some sort of backtracking: Remeber every point, where you have multiple choices to continue. Choose one way, and follow it. If it's a dead-end, go back to tha last point of decision and take the next choice. If no way leads to the exit, go to the previous last point and so on. This is a recursive approach, known as "depth-first-search" in graph theory (feel free to do a bit of googling, I'm confident, you'll find a lot of material about this :) ...)

HTH Martin