I'm trying to generate a maze and solve it if possible using DFS algorithm. I start by
generating a random maze then attempt to solve it if there is a solution. The maze is generated
randomly every time the code runs but the path of the generated maze is always the same and it
seems like there is always a path even though the maze is generated randomly.
#include <iostream>
#include <vector>
#include <random>
#include <algorithm>
#include <stack>
const int SIZE = 10;
enum Direction {
TOP,
RIGHT,
BOTTOM,
LEFT
};
struct Cell {
bool visited;
bool walls[4]; // top, right, bottom, left
Cell() {
visited = false;
std::fill(walls, walls + 4, true);
}
};
int getRandomNumber(int min, int max) {
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<int> dis(min, max);
return dis(gen);
}
bool isValidCell(int row, int col) {
return (row >= 0 && row < SIZE && col >= 0 && col < SIZE);
}
void removeWall(Cell& current, Cell& next, Direction direction) {
current.walls[direction] = false;
if (direction == TOP)
next.walls[BOTTOM] = false;
else if (direction == RIGHT)
next.walls[LEFT] = false;
else if (direction == BOTTOM)
next.walls[TOP] = false;
else if (direction == LEFT)
next.walls[RIGHT] = false;
}
void generateMaze(std::vector<std::vector<Cell>>& maze, int row, int col) {
static const int dx[] = {0, 1, 0, -1}; // right, down, left, up
static const int dy[] = {-1, 0, 1, 0};
maze[row][col].visited = true;
std::vector<int> directions = {TOP, RIGHT, BOTTOM, LEFT};
std::shuffle(directions.begin(), directions.end(), std::mt19937(std::random_device()()));
for (int direction : directions) {
int newRow = row + dy[direction];
int newCol = col + dx[direction];
if (isValidCell(newRow, newCol) && !maze[newRow][newCol].visited) {
removeWall(maze[row][col], maze[newRow][newCol], static_cast<Direction>(direction));
generateMaze(maze, newRow, newCol);
}
}
}
void generateMaze(std::vector<std::vector<Cell>>& maze) {
generateMaze(maze, 0, 0);
}
void displayMaze(const std::vector<std::vector<Cell>>& maze) {
for (int row = 0; row < SIZE; ++row) {
for (int col = 0; col < SIZE; ++col) {
std::cout << "+";
std::cout << (maze[row][col].walls[TOP] ? "---" : " ");
}
std::cout << "+\n";
for (int col = 0; col < SIZE; ++col) {
std::cout << (maze[row][col].walls[LEFT] ? "|" : " ");
std::cout << " ";
}
std::cout << "|\n";
}
for (int col = 0; col < SIZE; ++col) {
std::cout << "+---";
}
std::cout << "+\n";
}
bool solveMazeDFS(std::vector<std::vector<Cell>>& maze, int row, int col, std::vector<std::pair<int, int>>& path) {
static const int dx[] = {0, 1, 0, -1}; // right, down, left, up
static const int dy[] = {-1, 0, 1, 0};
if (!isValidCell(row, col) || maze[row][col].visited)
return false;
maze[row][col].visited = true;
if (row == SIZE - 1 && col == SIZE - 1) {
// Reached the end of the maze
path.push_back(std::make_pair(row, col));
return true;
}
for (int direction = 0; direction < 4; ++direction) {
int newRow = row + dy[direction];
int newCol = col + dx[direction];
if (solveMazeDFS(maze, newRow, newCol, path)) {
// Found a valid path, add the current cell to the path
path.push_back(std::make_pair(row, col));
return true;
}
}
return false;
}
bool solveMaze(std::vector<std::vector<Cell>>& maze, std::vector<std::pair<int, int>>& path) {
// Reset the visited flag of cells in the maze
for (int i = 0; i < SIZE; ++i) {
for (int j = 0; j < SIZE; ++j) {
maze[i][j].visited = false;
}
}
// Start solving the maze from the beginning
return solveMazeDFS(maze, 0, 0, path);
}
int main() {
std::vector<std::vector<Cell>> maze(SIZE, std::vector<Cell>(SIZE));
generateMaze(maze);
displayMaze(maze);
std::vector<std::pair<int, int>> path;
if (solveMaze(maze, path)) {
std::cout << "Solution:\n";
for (int i = path.size() - 1; i >= 0; --i) {
std::cout << "(" << path[i].first << ", " << path[i].second << ")";
if (i > 0)
std::cout << " -> ";
}
std::cout << std::endl;
} else {
std::cout << "No solution found.\n";
}
return 0;
}
Example of output:
+---+---+---+---+---+---+---+---+---+---+
| | |
+---+---+ + +---+---+---+---+---+ +
| | | | | |
+ +---+ + + +---+---+---+ + +
| | | | | |
+ + +---+ +---+---+ + +---+ +
| | | | | | | |
+ + +---+ + + +---+ +---+ +
| | | | | | | |
+ +---+ +---+ +---+ + + + +
| | | | | | | |
+ + +---+ +---+ +---+---+ + +
| | | | |
+ +---+ +---+---+---+---+---+---+ +
| | | | |
+---+ +---+---+ +---+ +---+ + +
| | | | | | |
+ +---+---+ +---+ +---+ +---+ +
| | |
+---+---+---+---+---+---+---+---+---+---+
Solution:
(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (0, 4) -> (0, 5) -> (0, 6) -> (0, 7) -> (0, 8) -> (0, 9) -> (1, 9) -> (2, 9) -> (3, 9) -> (4, 9) -> (5, 9) -> (6, 9) -> (7, 9) -> (8, 9) -> (9, 9)
The solution is always the same because only the outer boundaries are being detected in solveMazeDFS. The inner walls are completely ignored. That is why the solution always marches east until it hits the right edge and then south until it hits the bottom.
You could check for a wall and not recurse something like this:
if (not maze[row][col].walls[direction]) {
if (solveMazeDFS(maze, newRow, newCol, path)) {
// Found a valid path, add the current cell to the path
path.push_back(std::make_pair(row, col));
return true;
}
}
When run, this produces an actual solution:
+---+---+---+---+---+---+---+---+---+---+
| | | |
+ + +---+---+ +---+---+---+ + +
| | | | | | |
+ +---+---+ +---+---+ +---+ + +
| | | | | | |
+---+ + +---+ + +---+ + + +
| | | | | | | |
+ + + +---+---+---+ + + + +
| | | | | |
+ +---+---+---+ + +---+ +---+ +
| | | | | |
+---+---+ +---+---+ + +---+ + +
| | | | | | | |
+ + +---+ + + + + +---+ +
| | | | | | |
+ +---+ +---+---+---+ + + +---+
| | | | | | | |
+ + +---+ +---+ + + + + +
| | | | |
+---+---+---+---+---+---+---+---+---+---+
Solution:
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (3, 1) -> (4, 1) -> (4, 0) -> (5, 0) -> (5, 1) -> (5, 2)\
-> (6, 2) -> (6, 1) -> (7, 1) -> (7, 0) -> (8, 0) -> (9, 0) -> (9, 1) -> (8, 1) -> (8, 2) -> (7\
, 2) -> (7, 3) -> (6, 3) -> (6, 4) -> (7, 4) -> (7, 5) -> (6, 5) -> (5, 5) -> (4, 5) -> (4, 6) -\
> (3, 6) -> (3, 5) -> (2, 5) -> (2, 4) -> (3, 4) -> (3, 3) -> (3, 2) -> (2, 2) -> (2, 3) -> (1, \
3) -> (1, 4) -> (0, 4) -> (0, 5) -> (0, 6) -> (0, 7) -> (0, 8) -> (1, 8) -> (2, 8) -> (3, 8) -> \
(4, 8) -> (4, 9) -> (5, 9) -> (6, 9) -> (7, 9) -> (7, 8) -> (8, 8) -> (9, 8) -> (9, 9)
The generator guarantees the maze always has a path removing walls if necessary.