Introduction

A maze solver is a program designed to find a path through a maze from the start point to the destination. This is a fundamental problem in computer science and can be solved using different algorithms such as depth-first search (DFS), breadth-first search (BFS), and more. In this tutorial, we will implement a simple maze solver using depth-first search (DFS) in C++.

Objective

The objective of this program is to create an efficient maze solver in C++ that uses a depth-first search algorithm to find the path through a maze. The program will output whether there is a solution and display the solution path if one exists.

Code Implementation

#include 
#include 
using namespace std;

// Define the size of the maze
#define N 5
#define M 5

// Maze representation: 0 = path, 1 = wall
int maze[N][M] = {
    {0, 1, 0, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 0, 1, 0},
    {1, 1, 0, 1, 0},
    {0, 0, 0, 0, 0}
};

// Directions for moving in the maze (down, up, right, left)
int row_dir[] = {1, -1, 0, 0};
int col_dir[] = {0, 0, 1, -1};

// Function to check if a cell is valid
bool isValid(int x, int y) {
    return (x >= 0 && x < N && y >= 0 && y < M && maze[x][y] == 0);
}

// Function to solve the maze using DFS
bool solveMaze(int startX, int startY, int endX, int endY) {
    // Stack for DFS
    stack<pair<int, int>> s;
    bool visited[N][M] = {false};

    // Start from the initial position
    s.push({startX, startY});
    visited[startX][startY] = true;

    while (!s.empty()) {
        int x = s.top().first;
        int y = s.top().second;
        s.pop();

        // If we reached the destination
        if (x == endX && y == endY) {
            cout << "Path found!" << endl;
            return true;
        }

        // Explore all four directions
        for (int i = 0; i < 4; i++) {
            int newX = x + row_dir[i];
            int newY = y + col_dir[i];

            // If the new position is valid and not visited
            if (isValid(newX, newY) && !visited[newX][newY]) {
                s.push({newX, newY});
                visited[newX][newY] = true;
            }
        }
    }

    cout << "No path found!" << endl;
    return false;
}

int main() {
    int startX = 0, startY = 0; // Starting point
    int endX = 4, endY = 4;     // Destination point

    // Call the function to solve the maze
    solveMaze(startX, startY, endX, endY);
    return 0;
}
            

Explanation of the Program Structure

The program uses a depth-first search (DFS) algorithm to explore possible paths in the maze. The maze is represented as a 2D array, where ‘0’ indicates a free path, and ‘1’ represents a wall.

• isValid() function: This function checks if a given cell is within the maze boundaries and if it is an open path (value 0).
• solveMaze() function: This is the core of the program. It uses a stack to simulate the DFS approach. Starting from the start position, it explores all possible directions (down, up, right, left). If a valid path is found, it prints “Path found!” and returns true. If the stack becomes empty, indicating there is no path, it prints “No path found!”.
• main() function: This function initializes the start and end points of the maze and then calls the solveMaze() function to attempt to solve the maze.

How to Run the Program

1. Save the code in a file with a .cpp extension (e.g., maze_solver.cpp).
2. Open a terminal or command prompt.
3. Navigate to the directory where the file is saved.
4. Compile the program using a C++ compiler (e.g., g++ maze_solver.cpp -o maze_solver).
5. Run the compiled program (e.g., ./maze_solver on Linux or macOS, or maze_solver.exe on Windows).