_____      _        ____
| ____|_ __(_) ___  / ___| _ __   ___ _ __   ___ ___ _ __
|  _| | '__| |/ __| \___ \| '_ \ / _ \ '_ \ / __/ _ \ '__|
| |___| |  | | (__   ___) | |_) |  __/ | | | (_|  __/ |
|_____|_|  |_|\___| |____/| .__/ \___|_| |_|\___\___|_|
                          |_|                             

---

← back to index

Iterative Maze Solver Example

Iterative Maze Solver Example, a project by Eric Spencer.

---

Iterative/hasNext maze solver. A transcript of an exchange with ChatGPT about iterative maze solving in Java, in the context of a CS2 data structures course.

User

A CS2 course covers the main data structures in Java, following the ACM 2020 curricular guidelines. In that context, give coding examples of an iterative maze solver, and explain each step. The maze has a border and walls marked with '*', unvisited squares marked with a blank space ' ', and visited squares marked with 'x'.

ChatGPT

An iterative maze solver in Java, under those conventions:

import java.util.ArrayDeque;
import java.util.Queue;

public class MazeSolver {
    private static final char WALL = '*';
    private static final char UNVISITED = ' ';
    private static final char VISITED = 'x';

    public static void solveMaze(char[][] maze, int startX, int startY) {
        int rows = maze.length;
        int columns = maze[0].length;

        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{startX, startY});

        while (!queue.isEmpty()) {
            int[] currentPos = queue.poll();
            int x = currentPos[0];
            int y = currentPos[1];

            // Check if the current position is the maze exit
            if (isExit(x, y, rows, columns)) {
                System.out.println("Maze solved!");
                return;
            }

            // Mark the current position as visited
            maze[x][y] = VISITED;

            // Check and enqueue neighboring positions if they are valid and unvisited
            enqueueIfValid(queue, maze, x - 1, y);
            enqueueIfValid(queue, maze, x + 1, y);
            enqueueIfValid(queue, maze, x, y - 1);
            enqueueIfValid(queue, maze, x, y + 1);
        }

        System.out.println("No solution found.");
    }

    private static void enqueueIfValid(Queue<int[]> queue, char[][] maze, int x, int y) {
        int rows = maze.length;
        int columns = maze[0].length;

        if (x >= 0 && x < rows && y >= 0 && y < columns && maze[x][y] == UNVISITED) {
            queue.add(new int[]{x, y});
        }
    }

    private static boolean isExit(int x, int y, int rows, int columns) {
        return x == 0 || x == rows - 1 || y == 0 || y == columns - 1;
    }

    public static void main(String[] args) {
        char[][] maze = {
            {'*', '*', '*', '*', '*', '*', '*'},
            {'*', ' ', ' ', ' ', ' ', ' ', '*'},
            {'*', ' ', '*', '*', '*', ' ', '*'},
            {'*', ' ', '*', ' ', ' ', ' ', '*'},
            {'*', ' ', '*', '*', '*', '*', '*'},
            {'*', ' ', ' ', ' ', ' ', ' ', '*'},
            {'*', '*', '*', '*', '*', '*', '*'}
        };

        solveMaze(maze, 1, 1);
    }
}

The code works as follows.

1. The constants WALL, UNVISITED, and VISITED hold the characters used in the maze.
2. The solveMaze method takes the maze as a 2D character array (char[][]) and the starting coordinates startX and startY. It initializes a queue of positions to visit.
3. A while loop continues until the queue is empty. Inside the loop, the first position is removed with queue.poll() and its coordinates are assigned to x and y.
4. The isExit method checks whether the current position is the maze exit. If it is, the method prints "Maze solved!" and returns.
5. Otherwise the current position is marked as visited by setting maze[x][y] to VISITED.
6. Neighboring positions (up, down, left, right) are enqueued if they are valid and unvisited. The enqueueIfValid method performs that check.
7. If the queue empties without the exit being found, the method prints "No solution found."
8. The main method creates a sample maze as a 2D character array: a 7x7 grid surrounded by walls (*), with some open spaces ( ) and an entrance at (1, 1).
9. solveMaze is then called with the maze and the starting coordinates.

Started from (1, 1), the solver explores neighboring positions until it reaches the exit or exhausts the queue. Visited positions are marked with 'x'.

User

Is this method a breadth-first search?

ChatGPT

Yes. The solver above follows a breadth-first search (BFS).

BFS explores all nodes at the current level before moving to the next. In maze solving that means every neighbor of the current position is visited before the search moves deeper, so all positions at the same distance from the start are visited before any position at the next distance.

The Queue holds the traversal state. The search starts at the starting position, enqueues neighboring positions, and processes them in the order they were enqueued.

User

Is the example maze solvable?

ChatGPT

The example maze is not solvable. An isolated wall in the middle blocks every path to the exit.

The maze for reference:

*******
*     *
* *** *
* *   *
* ***** 
*     *
*******

The wall at row 4, column 3 disconnects the rest of the maze from the exit. No path exists from the starting position.

Two options follow: a different example maze that is solvable, or a modification of this one.

User

Make it solvable. Also allow the maze to have a starting point on the perimeter. The isExit function as written appears to prevent that.

ChatGPT

Both the maze and the isExit function change: the maze to make it solvable, isExit to accept a starting point on the perimeter.

Updated maze:

*********
*    *  *
* ** *  *
*    *  *
*  ***** 
*       *
*********

The starting position may now sit on the perimeter, and a path to the exit exists.

Updated code with the modified isExit function:

import java.util.ArrayDeque;
import java.util.Queue;

public class MazeSolver {
    private static final char WALL = '*';
    private static final char UNVISITED = ' ';
    private static final char VISITED = 'x';

    public static void solveMaze(char[][] maze, int startX, int startY) {
        int rows = maze.length;
        int columns = maze[0].length;

        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{startX, startY});

        while (!queue.isEmpty()) {
            int[] currentPos = queue.poll();
            int x = currentPos[0];
            int y = currentPos[1];

            // Check if the current position is the maze exit
            if (isExit(x, y, rows, columns)) {
                System.out.println("Maze solved!");
                return;
            }

            // Mark the current position as visited
            maze[x][y] = VISITED;

            // Check and enqueue neighboring positions if they are valid and unvisited
            enqueueIfValid(queue, maze, x - 1, y);
            enqueueIfValid(queue, maze, x + 1, y);
            enqueueIfValid(queue, maze, x, y - 1);
            enqueueIfValid(queue, maze, x, y + 1);
        }

        System.out.println("No solution found.");
    }

    private static void enqueueIfValid(Queue<int[]> queue, char[][] maze, int x, int y) {
        int rows = maze.length;
        int columns = maze[0].length;

        if (x >= 0 && x < rows && y >= 0 && y < columns && maze[x][y] == UNVISITED) {
            queue.add(new int[]{x, y});
        }
    }

    private static boolean isExit(int x, int y, int rows, int columns) {
        return x == 0 || x == rows - 1 || y == 0 || y == columns - 1;
    }

    public static void main(String[] args) {
        char[][] maze = {
            {'*', '*', '*', '*', '*', '*', '*', '*', '*'},
            {'*', ' ', ' ', ' ', '*', ' ', ' ', ' ', '*'},
            {'*', ' ', '*', '*', ' ', ' ', '*', ' ', '*'},
            {'*', ' ', ' ', ' ', '*', ' ', ' ', ' ', '*'},
            {'*', ' ', ' ', '*', '*', '*', '*', ' ', '*'},
            {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
            {'*', '*', '*', '*', '*', '*', '*', '*', '*'}
        };

        solveMaze(maze, 1, 1);
    }
}

User

That maze still does not look solvable. Also, if movement is restricted to the cardinal directions, a solution on the perimeter reachable only by a diagonal move will not work.

ChatGPT

Correct. Allowing the starting position on the perimeter does not by itself make the maze solvable. The maze changes again, and the starting position with it.

Updated solvable maze:

*********
*       *
* *** * *
* *   * *
* ***** 
*       *
*********

A passage runs from the starting position to the exit.

Updated code with the modified maze:

import java.util.ArrayDeque;
import java.util.Queue;

public class MazeSolver {
    private static final char WALL = '*';
    private static final char UNVISITED = ' ';
    private static final char VISITED = 'x';

    public static void solveMaze(char[][] maze, int startX, int startY) {
        int rows = maze.length;
        int columns = maze[0].length;

        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{startX, startY});

        while (!queue.isEmpty()) {
            int[] currentPos = queue.poll();
            int x = currentPos[0];
            int y = currentPos[1];

            // Check if the current position is the maze exit
            if (isExit(x, y, rows, columns)) {
                System.out.println("Maze solved!");
                return;
            }

            // Mark the current position as visited
            maze[x][y] = VISITED;

            // Check and enqueue neighboring positions if they are valid and unvisited
            enqueueIfValid(queue, maze, x - 1, y);
            enqueueIfValid(queue, maze, x + 1, y);
            enqueueIfValid(queue, maze, x, y - 1);
            enqueueIfValid(queue, maze, x, y + 1);
        }

        System.out.println("No solution found.");
    }

    private static void enqueueIfValid(Queue<int[]> queue, char[][] maze, int x, int y) {
        int rows = maze.length;
        int columns = maze[0].length;

        if (x >= 0 && x < rows && y >= 0 && y < columns && maze[x][y] == UNVISITED) {
            queue.add(new int[]{x, y});
        }
    }

    private static boolean isExit(int x, int y, int rows, int columns) {
        return x == 0 || x == rows - 1 || y == 0 || y == columns - 1;
    }

    public static void main(String[] args) {
        char[][] maze = {
            {'*', '*', '*', '*', '*', '*', '*', '*', '*'},
            {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
            {'*', ' ', '*', '*', ' ', '*', ' ', ' ', '*'},
            {'*', ' ', '*', ' ', ' ', '*', ' ', ' ', '*'},
            {'*', ' ', '*', '*', '*', '*', ' ', ' ', '*'},
            {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
            {'*', '*', '*', '*', '*', '*', '*', '*', '*'}
        };

        solveMaze(maze, 1, 1);
    }
}

The starting position is (1, 1), the top left corner of the maze.

User

Try another maze to solve.

ChatGPT

A new solvable maze:

*********
*       *
* *** * *
* *   * *
* * * * *
*   *   *
*********

A path runs from the starting position to the exit.

The code with the new maze:

import java.util.ArrayDeque;
import java.util.Queue;

public class MazeSolver {
    private static final char WALL = '*';
    private static final char UNVISITED = ' ';
    private static final char VISITED = 'x';

    public static void solveMaze(char[][] maze, int startX, int startY) {
        int rows = maze.length;
        int columns = maze[0].length;

        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{startX, startY});

        while (!queue.isEmpty()) {
            int[] currentPos = queue.poll();
            int x = currentPos[0];
            int y = currentPos[1];

            // Check if the current position is the maze exit
            if (isExit(x, y, rows, columns)) {
                System.out.println("Maze solved!");
                return;
            }

            // Mark the current position as visited
            maze[x][y] = VISITED;

            // Check and enqueue neighboring positions if they are valid and unvisited
            enqueueIfValid(queue, maze, x - 1, y);
            enqueueIfValid(queue, maze, x + 1, y);
            enqueueIfValid(queue, maze, x, y - 1);
            enqueueIfValid(queue, maze, x, y + 1);
        }

        System.out.println("No solution found.");
    }

    private static void enqueueIfValid(Queue<int[]> queue, char[][] maze, int x, int y) {
        int rows = maze.length;
        int columns = maze[0].length;

        if (x >= 0 && x < rows && y >= 0 && y < columns && maze[x][y] == UNVISITED) {
            queue.add(new int[]{x, y});
        }
    }

    private static boolean isExit(int x, int y, int rows, int columns) {
        return x == 0 || x == rows - 1 || y == 0 || y == columns - 1;
    }

    public static void main(String[] args) {
        char[][] maze = {
            {'*', '*', '*', '*', '*', '*', '*', '*', '*'},
            {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
            {'*', ' ', '*', '*', ' ', '*', ' ', ' ', '*'},
            {'*', ' ', '*', ' ', ' ', '*', ' ', ' ', '*'},
            {'*', ' ', '*', ' ', '*', '*', ' ', ' ', '*'},
            {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
            {'*', '*', '*', '*', '*', '*', '*', '*', '*'}
        };

        solveMaze(maze, 1, 1);
    }
}

The starting position is (1, 1), the top left corner of the maze.

User

Try making a maze of size 4x4.

ChatGPT

A solvable 4x4 maze:

****
*   *
* * *
*   *
****

A path runs from the starting position to the exit.

The code with the new maze:

import java.util.ArrayDeque;
import java.util.Queue;

public class MazeSolver {
    private static final char WALL = '*';
    private static final char UNVISITED = ' ';
    private static final char VISITED = 'x';

    public static void solveMaze(char[][] maze, int startX, int startY) {
        int rows = maze.length;
        int columns = maze[0].length;

        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{startX, startY});

        while (!queue.isEmpty()) {
            int[] currentPos = queue.poll();
            int x = currentPos[0];
            int y = currentPos[1];

            // Check if the current position is the maze exit
            if (isExit(x, y, rows, columns)) {
                System.out.println("Maze solved!");
                return;
            }

            // Mark the current position as visited
            maze[x][y] = VISITED;

            // Check and enqueue neighboring positions if they are valid and unvisited
            enqueueIfValid(queue, maze, x - 1, y);
            enqueueIfValid(queue, maze, x + 1, y);
            enqueueIfValid(queue, maze, x, y - 1);
            enqueueIfValid(queue, maze, x, y + 1);
        }

        System.out.println("No solution found.");
    }

    private static void enqueueIfValid(Queue<int[]> queue, char[][] maze, int x, int y) {
        int rows = maze.length;
        int columns = maze[0].length;

        if (x >= 0 && x < rows && y >= 0 && y < columns && maze[x][y] == UNVISITED) {
            queue.add(new int[]{x, y});
        }
    }

    private static boolean isExit(int x, int y, int rows, int columns) {
        return x == 0 || x == rows - 1 || y == 0 || y == columns - 1;
    }

    public static void main(String[] args) {
        char[][] maze = {
            {'*', '*', '*', '*'},
            {'*', ' ', ' ', '*'},
            {'*', ' ', '*', '*'},
            {'*', ' ', ' ', '*'},
            {'*', '*', '*', '*'}
        };

        solveMaze(maze, 1, 1);
    }
}

The starting position is (1, 1), the top left corner of the maze.

User

What are the advantages of using an iterative approach for maze solving compared to a recursive approach?

ChatGPT

Five advantages.

1. Iterative algorithms typically use less memory. Recursion relies on the function call stack to hold intermediate state, which can be substantial for large mazes or deeply nested recursion. An iterative solver holds that state in a queue or a stack instead.
2. Recursion depth is bounded by the system stack size. A very large or complex maze can exceed that limit and produce a stack overflow error. Iterative algorithms do not use the call stack for search state.
3. Control flow is more explicit. An iterative maze solver runs as a sequential loop, so its progress is easier to follow and debug than a chain of recursive calls.
4. Iterative algorithms are easier to modify or extend. Because the state lives in an ordinary queue or stack, extra conditions, checks, and changes of behavior can be introduced without changing the call structure.
5. Some languages support tail recursion optimization, which removes the extra stack space required by recursive calls. Not all languages or compilers provide it. Where it is absent, the iterative form is the more reliable choice.

User

How can a maze be represented using data structures suitable for iterative maze solving?

ChatGPT

A maze can be represented as a two-dimensional array or as a grid-based data structure.

A two-dimensional array:

char[][] maze = {
    {'*', '*', '*', '*', '*', '*'},
    {'*', ' ', ' ', ' ', ' ', '*'},
    {'*', '*', '*', '*', ' ', '*'},
    {'*', ' ', ' ', ' ', ' ', '*'},
    {'*', '*', '*', '*', '*', '*'}
};

Each cell of the maze is one character. '*' is a wall or obstacle, ' ' (space) is an unvisited or empty cell, and any other character can mark a different type of cell, such as the starting position or the exit.

The other option is a grid-based data structure, such as a two-dimensional ArrayList or a custom MazeCell class:

List<List<Character>> maze = new ArrayList<>();
maze.add(Arrays.asList('*', '*', '*', '*', '*', '*'));
maze.add(Arrays.asList('*', ' ', ' ', ' ', ' ', '*'));
maze.add(Arrays.asList('*', '*', '*', '*', ' ', '*'));
maze.add(Arrays.asList('*', ' ', ' ', ' ', ' ', '*'));
maze.add(Arrays.asList('*', '*', '*', '*', '*', '*'));

The grid-based form resizes dynamically. It costs more memory and slower access than a plain two-dimensional array.

User

Which iterative algorithms are commonly used for maze solving, and how do they work?

ChatGPT

Two are common: breadth-first search and depth-first search.

Breadth-first search (BFS)

• BFS visits all cells at the same depth before moving to the next depth level. It starts at the source cell, usually the starting position, and explores all its neighbors before moving on to their neighbors.
• A queue keeps track of the cells still to be explored. Neighboring cells are enqueued and processed in the order they were discovered.
• Each cell is marked as visited. That prevents revisiting and records the path taken.
• BFS finds the shortest path from the source cell to the destination cell, so it is optimal in the number of steps required.
• The queue is typically an ArrayDeque in Java.

Depth-first search (DFS)

• DFS traverses as far as possible along each branch before backtracking. It starts at the source cell and explores one path to a dead end, then backtracks and explores another.
• A stack keeps track of the cells still to be explored. Neighboring cells are pushed and processed in the order they were discovered.
• Each cell is marked as visited. That prevents revisiting and records the path taken.
• DFS does not guarantee the shortest path. It is often simpler to implement than BFS and suits cases such as maze generation or the search for any valid path.
• The stack is typically an ArrayDeque in Java.

The choice between the two depends on whether the shortest path is required or any valid path will do.

User

Are there more?

ChatGPT

Two more.

Iterative deepening depth-first search (IDDFS)

• IDDFS combines BFS and DFS. It performs a series of DFS searches with increasing depth limits, starting from a depth of 0 and incrementing the limit by one in each iteration.
• Each pass is a depth-limited DFS that records the visited cells along the path. If the destination is not found within the limit, the limit rises and the search repeats.
• IDDFS finds the shortest path, as BFS does, but the depth-limited search avoids the high memory consumption of BFS.
• The implementation uses a stack and a depth counter.

A* search

• A* search is an informed search algorithm that uses heuristic estimates to guide the search toward the goal. Each cell is scored on a combination of the cost to reach that cell and an estimated cost from that cell to the destination.
• A priority queue stores the cells, ordered by that combined score. The algorithm expands the cell with the lowest total estimated cost.
• A* search gives an optimal solution, the shortest path, if the heuristic estimate is admissible (never overestimates the actual cost) and consistent (satisfies the monotonicity property).
• The heuristic function estimates the cost from a given cell to the destination. Manhattan distance, Euclidean distance, and other distance measures are common choices.
• The implementation uses a priority queue.

User

What is Manhattan distance?

ChatGPT

Manhattan distance is a distance measure for grid-based environments, such as mazes, where movement is restricted to horizontal and vertical directions and no diagonal movement is allowed. It is named after the city block layout of Manhattan, where the shortest distance between two points is measured along the grid lines.

In maze solving and pathfinding, Manhattan distance is the minimum number of horizontal and vertical moves required to reach a target position from a given position. It is the sum of the absolute differences between the x-coordinates and between the y-coordinates of the two positions.

Formally, the Manhattan distance between two points (x1, y1) and (x2, y2) is:

Manhattan distance = |x2 - x1| + |y2 - y1|

For two points A(3, 5) and B(8, 2), the absolute differences give:

|8 - 3| + |2 - 5| = 5 + 3 = 8

The Manhattan distance between A(3, 5) and B(8, 2) is 8. A* search uses it as a heuristic to estimate the distance between a given cell and the destination.

User

Are there more algorithms not yet mentioned?

ChatGPT

Two more.

Best-first search (greedy search)

• Best-first search is an informed search algorithm that selects the most promising cell from a heuristic function alone, without regard to the actual path cost.
• A priority queue stores the cells, ordered only by the heuristic value for each cell.
• At each step the algorithm takes the cell with the highest priority, that is, the one with the lowest heuristic value, and expands it.
• Best-first search does not guarantee an optimal solution. With a well-designed heuristic function it can be economical in memory and fast to explore.

Recursive division method

• The recursive division method is a maze generation algorithm that divides the maze space into rooms and passages recursively.
• It starts with a solid maze grid and divides the grid with walls in a random direction until the intended maze structure is reached.
• At each recursive step a random wall is selected and removed, which opens a passage between adjacent rooms.
• The recursive division continues until the intended structure is obtained. The result has a complex branching structure.
• The implementation uses recursive function calls.

User

Are there even more algorithms?

ChatGPT

Three more.

Wall follower (left-hand rule or right-hand rule)

• The wall follower algorithm is a simple and commonly used method for maze solving. It follows either the left-hand or the right-hand wall while traversing the maze.
• It starts at an entrance point and continuously follows the chosen wall as it moves through the maze.
• Sticking to one wall eventually reaches the exit, if there is one, or returns to the starting point in the case of a cyclic maze.
• The path found is not necessarily the shortest. The method gives a systematic way to explore and solve a maze without an explicit graph search.
• The choice between the left-hand rule and the right-hand rule determines the specific path taken.

Randomized Prim's algorithm

• Randomized Prim's algorithm is a maze generation algorithm based on the minimum spanning tree concept.
• It starts with a grid of cells in which each cell is initially a separate component.
• It selects a cell at random and adds it to the maze, then selects a random neighboring cell that is not yet in the maze and connects it by removing the wall between the two.
• The process continues by repeatedly selecting a random cell from the boundary of the maze and connecting it to an adjacent cell already part of the maze.
• Every cell ends up reachable from every other cell, and the maze has a branching structure.
• A priority queue makes the selection of the next cell to add efficient.

Kruskal's algorithm

• Kruskal's algorithm is a minimum spanning tree algorithm that can be adapted for maze generation.
• It starts with a grid of cells in which each cell is initially a separate component.
• It creates a list of all the walls between cells in random order, then iterates over the list and selectively removes walls, joining the components of the cells they separate.
• The process continues until all cells are part of the same component and the maze is connected.
• The result is a random, interconnected layout in which each cell is reachable from any other cell.
• A disjoint-set data structure merges components and checks connectivity.

User

List a few more.

ChatGPT

Three more.

Dead-end filling

• Dead-end filling is a maze-solving algorithm that eliminates dead-end paths in the maze.
• It starts at the entrance of the maze and explores until it reaches a dead end.
• At a dead end it marks the path as visited and backtracks to the previous junction.
• At each junction it checks whether all adjacent paths have been visited. If they have, the junction is itself marked as a dead end and the backtracking continues.
• Dead ends are eliminated one by one until only valid paths remain, which leaves the solution.
• The algorithm finds a solution if one exists, and it simplifies the maze by removing unnecessary dead ends.

Trémaux's algorithm

• Trémaux's algorithm is an algorithm for maze exploration that finds a solution if one exists.
• Each path it traverses is marked with either one or two marks, called threads.
• On entering a new intersection the algorithm checks for unmarked paths. If there are any, it chooses one and proceeds, marking it with a single thread.
• If all paths at an intersection already carry a single thread, the algorithm follows the thread that has the fewest marks.
• On reaching the exit or a dead end, the algorithm retraces its steps along the threads in reverse order.
• Every path in the maze is traversed at least once.

Hunt and kill

• The hunt and kill algorithm is a maze generation algorithm that combines random exploration with a backtracking mechanism.
• It starts by selecting a starting cell at random and moving through the maze, carving passages.
• At a dead end it "kills" that path by backtracking until it finds an unvisited cell adjacent to a visited cell.
• It then resumes carving passages from that cell and continues the random exploration.
• The process continues until all cells have been visited. The result is a fully connected maze with no dead ends.
• Mazes from hunt and kill have a more natural, organic look than those from other algorithms.

User

List more.

ChatGPT

Three more.

Eller's algorithm

• Eller's algorithm is a maze generation algorithm that works row by row, and each row is connected to the previous row.
• It starts with a grid of cells in which each cell is initially in a separate set or group.
• It iterates through each row and merges cells horizontally with a certain probability.
• Vertical connections come from selecting representative cells from each set in the previous row and merging them with cells in the current row.
• Because each row connects to the previous one, the maze has vertical passages and a natural progression from one row to the next.

Wilson's algorithm

• Wilson's algorithm is a maze generation algorithm that generates mazes by random walks that run until they encounter unvisited cells.
• It starts with a randomly chosen cell and performs a random walk until it reaches a cell that has already been visited.
• When a loop is detected, the algorithm eliminates it by backtracking along the random walk and marking each cell as visited.
• This repeats until all cells in the maze have been visited. The result is a fully connected maze without loops or dead ends.
• The random component is strong, and the mazes tend to have long, winding passages.

Binary tree algorithm

• The binary tree algorithm is a simple, straightforward maze generation algorithm that operates on a grid of cells.
• It iterates through each cell in the maze and randomly connects it either to the cell to the north or to the cell to the west.
• The binary choice made for each cell produces a maze with a grid-like structure and a high prevalence of vertical and horizontal passages.
• It is easy to implement and computationally efficient, which suits simple maze generation scenarios.

User

How can complex maze structures, such as mazes with loops or multiple entry and exit points, be handled with an iterative approach?

ChatGPT

Complex maze structures call for adapted algorithms or new strategies. Four approaches.

Modified depth-first search

• The traditional DFS algorithm can be modified for mazes with loops or multiple entry and exit points.
• Instead of terminating the search when the destination is found, the search continues until all possible paths have been explored.
• The search then finds all possible solutions or exit points in the maze rather than stopping at the first one.
• Additional data structures serve the modified DFS: a stack to maintain the current path, and a set to track visited cells.

Backtracking algorithms

• Backtracking algorithms, such as the wall follower algorithm or Trémaux's algorithm, handle mazes with loops and multiple entry and exit points.
• They explore the maze while maintaining a record of visited cells and the path taken.
• On a dead end or on revisiting a visited cell, the algorithm backtracks along the path until it finds an unexplored option.
• Backtracking lets them cover all possible paths and find multiple exit points or loops in the maze.

Graph traversal algorithms

• The maze can be represented as a graph and traversed with breadth-first search or depth-first search.
• Treated as a graph, the maze can be navigated to discover all possible paths and to identify loops or multiple entry and exit points.
• Graph traversal handles various maze configurations, including those with loops, multiple solutions, or disconnected regions.
• Adjacency lists or matrices represent the maze as a graph, and the chosen traversal algorithm is adapted to the representation.

Iterative maze generation

• During maze generation, iterative algorithms give more flexibility and control over the structure of the maze.
• Randomized Prim's algorithm or the hunt and kill algorithm can be modified to build loops or multiple entry and exit points into the generated maze.
• Additional rules or conditions during the generation process control the presence of loops or multiple pathways.

User

Is there a way to show every single step the algorithm takes as it works through the maze?

ChatGPT

Four approaches.

Graphical user interface

• A GUI application displays the maze grid and updates it as the algorithm progresses.
• Graphical elements such as cells, walls, and markers represent the maze and the movements of the algorithm.
• The GUI is updated at each step to show the current state of the maze and the action taken.
• The visualization is real time.

Console output

• The maze grid and the actions of the algorithm are printed to the console window at each step.
• The printout marks visited cells, the current position, and any change the algorithm made.
• Decisions such as which path to take or how an obstacle was resolved can be printed alongside.
• The representation is textual.

Animation

• A graphics library or framework produces an animated visualization of the steps.
• Graphical elements represent the maze and the movements of the algorithm.
• The animation is updated frame by frame with the actions taken, the changes to the maze, and the exploration process.

Step-by-step logging

• A logging mechanism in the code records each step of execution.
• The log holds relevant information: the current state of the maze, the action taken, and any change made.
• After the algorithm completes, or at specific intervals, the logged data is analyzed and visualizations are generated from it.
• Logging separates recording from display, so how and when to visualize the recorded steps can be decided later.

User

Provide Java code that outputs each step to the console as described above.

ChatGPT

Java code that prints each step of a maze-solving algorithm to the console:

public class MazeSolver {
    private char[][] maze;  // The maze represented as a 2D character array
    private int startRow;   // Starting row index
    private int startCol;   // Starting column index
    private int endRow;     // Ending row index
    private int endCol;     // Ending column index

    public MazeSolver(char[][] maze, int startRow, int startCol, int endRow, int endCol) {
        this.maze = maze;
        this.startRow = startRow;
        this.startCol = startCol;
        this.endRow = endRow;
        this.endCol = endCol;
    }

    public void solveMaze() {
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        // Initialize visited array to keep track of visited cells

        solve(startRow, startCol, visited);
    }

    private boolean solve(int row, int col, boolean[][] visited) {
        // Check if the current position is out of bounds or a wall
        if (row < 0 || row >= maze.length || col < 0 || col >= maze[0].length || maze[row][col] == '*') {
            return false;
        }

        // Check if the current position is the destination
        if (row == endRow && col == endCol) {
            return true;
        }

        // Check if the current position has already been visited
        if (visited[row][col]) {
            return false;
        }

        // Mark the current position as visited
        visited[row][col] = true;

        // Output the current state of the maze
        printMaze();

        // Recursively explore neighboring cells
        if (solve(row - 1, col, visited)) {
            return true;
        }
        if (solve(row + 1, col, visited)) {
            return true;
        }
        if (solve(row, col - 1, visited)) {
            return true;
        }
        if (solve(row, col + 1, visited)) {
            return true;
        }

        // If none of the neighboring cells leads to the destination, backtrack
        visited[row][col] = false;

        // Output the backtracked state of the maze
        printMaze();

        return false;
    }

    private void printMaze() {
        for (char[] row : maze) {
            for (char cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {
        char[][] maze = {
                {'*', '*', '*', '*', '*', '*', '*', '*', '*'},
                {'*', ' ', ' ', ' ', '*', ' ', ' ', ' ', '*'},
                {'*', ' ', '*', ' ', '*', ' ', '*', ' ', '*'},
                {'*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*'},
                {'*', ' ', '*', '*', '*', '*', '*', ' ', '*'},
                {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
                {'*', '*', '*', '*', '*', '*', '*', '*', '*'}
        };

        int startRow = 1;
        int startCol = 1;
        int endRow = 5;
        int endCol = 7;

        MazeSolver solver = new MazeSolver(maze, startRow, startCol, endRow, endCol);
        solver.solveMaze();
    }
}

This solver is recursive. It prints the current state of the maze at each step, including the backtracked state where that applies. The maze is a 2D character array in which '*' denotes a wall and ' ' an unvisited cell. Other characters can carry additional symbols.

At each step of the solve the maze is written to the console, so the progress of the algorithm and its route toward the destination are visible.

The maze shown is a simple example and can be replaced with any other configuration.

User

How would the next() function work to retrieve the next move or location in the maze traversal?

ChatGPT

A next() function that returns the next move or location can be added to the existing maze-solving code:

public class MazeSolver {
    // ...

    private List<int[]> path;  // List to store the path taken during traversal
    private int currentStep;   // Index of the current step in the path list

    public MazeSolver(char[][] maze, int startRow, int startCol, int endRow, int endCol) {
        // ...
        path = new ArrayList<>();
        currentStep = 0;
    }

    public int[] next() {
        if (currentStep >= path.size()) {
            // Traversal has been completed, return null or handle end of traversal as needed
            return null;
        }

        int[] nextMove = path.get(currentStep);
        currentStep++;
        return nextMove;
    }

    // ...

    private boolean solve(int row, int col, boolean[][] visited) {
        // ...

        // Recursively explore neighboring cells
        if (solve(row - 1, col, visited)) {
            path.add(new int[]{row - 1, col});  // Add the current move to the path list
            return true;
        }
        if (solve(row + 1, col, visited)) {
            path.add(new int[]{row + 1, col});  // Add the current move to the path list
            return true;
        }
        if (solve(row, col - 1, visited)) {
            path.add(new int[]{row, col - 1});  // Add the current move to the path list
            return true;
        }
        if (solve(row, col + 1, visited)) {
            path.add(new int[]{row, col + 1});  // Add the current move to the path list
            return true;
        }

        // ...
    }

    // ...
}

A path list stores the path taken during the traversal. Each element of path is a move or location in the maze, held as an array of two integers [row, col].

The next() function returns the element at the currentStep index in the path list, then increments currentStep to point at the following move.

next() is called repeatedly until it returns null, or until whatever end-of-traversal condition applies.

The solve() method must also be changed to append the current move or location to the path list whenever the algorithm chooses a valid neighboring cell.

User

Make sure the function is iterative, not recursive.

ChatGPT

An iterative next() function can be built on breadth-first search or depth-first search with a stack or a queue.

A stack-based depth-first search:

import java.util.*;

public class MazeSolver {
    private char[][] maze;  // The maze represented as a 2D character array
    private int startRow;   // Starting row index
    private int startCol;   // Starting column index
    private int endRow;     // Ending row index
    private int endCol;     // Ending column index

    public MazeSolver(char[][] maze, int startRow, int startCol, int endRow, int endCol) {
        this.maze = maze;
        this.startRow = startRow;
        this.startCol = startCol;
        this.endRow = endRow;
        this.endCol = endCol;
    }

    public int[] next() {
        Stack<int[]> stack = new Stack<>();
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        stack.push(new int[]{startRow, startCol});

        while (!stack.isEmpty()) {
            int[] current = stack.pop();
            int row = current[0];
            int col = current[1];
            visited[row][col] = true;

            // Check if the current position is the destination
            if (row == endRow && col == endCol) {
                return current;
            }

            // Explore neighboring cells
            if (row - 1 >= 0 && !visited[row - 1][col] && maze[row - 1][col] != '*') {
                stack.push(new int[]{row - 1, col});
            }
            if (row + 1 < maze.length && !visited[row + 1][col] && maze[row + 1][col] != '*') {
                stack.push(new int[]{row + 1, col});
            }
            if (col - 1 >= 0 && !visited[row][col - 1] && maze[row][col - 1] != '*') {
                stack.push(new int[]{row, col - 1});
            }
            if (col + 1 < maze[0].length && !visited[row][col + 1] && maze[row][col + 1] != '*') {
                stack.push(new int[]{row, col + 1});
            }
        }

        // No more moves, traversal is complete
        return null;
    }

    public static void main(String[] args) {
        char[][] maze = {
                {'*', '*', '*', '*', '*', '*', '*', '*', '*'},
                {'*', ' ', ' ', ' ', '*', ' ', ' ', ' ', '*'},
                {'*', ' ', '*', ' ', '*', ' ', '*', ' ', '*'},
                {'*', ' ', '*', ' ', ' ', ' ', '*', ' ', '*'},
                {'*', ' ', '*', '*', '*', '*', '*', ' ', '*'},
                {'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*'},
                {'*', '*', '*', '*', '*', '*', '*', '*', '*'}
        };

        int startRow = 1;
        int startCol = 1;
        int endRow = 5;
        int endCol = 7;

        MazeSolver solver = new MazeSolver(maze, startRow, startCol, endRow, endCol);
        int[] nextMove;
        while ((nextMove = solver.next()) != null) {
            int row = nextMove[0];
            int col = nextMove[1];
            System.out.println("Next move: (" + row + ", " + col + ")");
        }
    }
}

The next() function uses a stack to perform an iterative depth-first search of the maze. It visits each cell and checks whether it is the destination. If the current cell is the destination, it returns the current position as the next move. Otherwise it explores neighboring cells and pushes them onto the stack if they are valid and unvisited.

In the main() method, next() is called in a loop until it returns null, and each retrieved move is printed to the console.

User

How can complex maze structures or multiple solutions be handled using the iterator-based approach?

ChatGPT

The iterator-based maze solver needs changes to support these cases.

Multiple solutions

• Modify the next() function to return a list of moves instead of a single move, so that all possible moves at each step are available.
• Adapt the algorithm to continue exploring all possible paths instead of terminating when the destination is reached. Removing the termination condition lets the algorithm explore all valid neighboring cells.
• Keep every path or solution found during the traversal in a data structure such as a list of lists or a list of arrays.

Complex maze structures

• Extend the maze representation for loops, multiple entry and exit points, or special symbols denoting other complex maze elements.
• Adjust the maze-solving algorithm for the new features or symbols. Additional conditions or rules determine which moves are valid at a loop or where there are multiple entry and exit points.
• Consider A* or Dijkstra's algorithm for complex maze structures and optimal paths.

User

Which data structures and algorithms support the iterator-based maze solver efficiently?

ChatGPT

Five options.

Graph data structure

• Represent the maze as a graph in which each cell is a vertex and the connections between cells are the possible moves.
• Store the graph as an adjacency list or an adjacency matrix, depending on the density of connections in the maze.
• The representation supports traversal and path finding with depth-first search or breadth-first search.

Breadth-first search

• BFS is widely used for maze solving because it is efficient and finds the shortest path.
• It explores the maze breadth-wise, visiting all reachable cells at a given distance before moving to the next distance level.
• For the iterator-based approach, a queue stores the cells to be visited next.

Depth-first search

• DFS explores the maze by visiting cells as deeply as possible before backtracking.
• It can be implemented iteratively with a stack that keeps track of the cells to be visited.
• DFS is useful for generating multiple solutions and for exploring complex maze structures.

A* algorithm

• A* is an informed search algorithm that uses heuristics to find the optimal path between two points efficiently.
• It evaluates each potential move on a combination of the cost to reach the current cell and an estimated cost to reach the destination.
• A* is advantageous where additional information about the maze is available, such as distances or weights assigned to cells.
• For the iterator-based approach, a priority queue orders cells by their evaluation scores.

Disjoint-set data structure (union-find)

• In a maze with loops or other complex structures, a disjoint-set data structure detects and handles cycles.
• It tracks and merges sets of connected cells during traversal, which stops the search from getting stuck in loops.
• It also determines the connectivity of cells in the maze.

Thread generated with ChatGPT [https://chat.openai.com] and downloaded with Botrush [https://botrush.io]