Eric Spencer
projects
Recursive maze solver. A transcript of an exchange with ChatGPT about maze-solving code in Java, framed around a CS2 data structures course. In the maze notation used throughout, '*' is a wall, '.' an unvisited square, '-' a dead-end, '0' the starting point, and '+' a visited space.
A recursive maze solver in Java:
public class MazeSolver {
private char[][] maze;
private int rows;
private int cols;
private int startRow;
private int startCol;
public MazeSolver(char[][] maze) {
this.maze = maze;
this.rows = maze.length;
this.cols = maze[0].length;
findStart();
}
private void findStart() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (maze[i][j] == '0') {
startRow = i;
startCol = j;
return;
}
}
}
}
public void solve() {
solveMaze(startRow, startCol);
}
private boolean solveMaze(int row, int col) {
if (row < 0 || col < 0 || row >= rows || col >= cols) {
return false; // outside of maze boundary
}
if (maze[row][col] == '*' || maze[row][col] == '+' || maze[row][col] == '-') {
return false; // wall or visited space
}
if (maze[row][col] == '.') {
maze[row][col] = '+'; // mark as visited
if (row == 0 || col == 0 || row == rows - 1 || col == cols - 1) {
return true; // reached the exit
}
// Recursive calls in all four directions
boolean foundExit = solveMaze(row - 1, col) || // up
solveMaze(row + 1, col) || // down
solveMaze(row, col - 1) || // left
solveMaze(row, col + 1); // right
if (foundExit) {
return true; // found the exit
} else {
maze[row][col] = '-'; // mark as dead-end
return false; // backtrack
}
}
return false; // obstacle or already visited
}
}
The code step by step:
MazeSolver class holds the maze-solving functionality. It takes a 2D character array (maze) as input, which represents the maze structure with the symbols above.findStart() locates the starting position marked with '0'.solve() is the entry point. It calls solveMaze() with the starting position as the initial parameters.solveMaze() performs the recursive algorithm. It takes the current row and column as input.solveMaze() check whether the current position is outside the maze boundaries, a wall ('*'), a visited space ('+'), or a dead-end ('-'). Any of these returns false and backtracks.true.||).true, an exit was found and the method returns true.false, the position is a dead-end. The method changes it to '-' and returns false to backtrack.An instance of MazeSolver is constructed with the maze as input, and solve() finds the solution. The maze is modified in place: '+' marks the path to the exit, '-' marks dead-ends.
The solver assumes exactly one starting position ('0') and exactly one path to the exit. A maze that does not satisfy those assumptions may not solve correctly.
An example maze as a 2D character array:
char[][] maze = {
{'*', '*', '*', '*', '*', '*', '*', '*', '*'},
{'*', '0', '.', '.', '*', '.', '*', '.', '*'},
{'*', '*', '*', '.', '*', '.', '*', '.', '*'},
{'*', '.', '.', '.', '.', '.', '*', '.', '*'},
{'*', '*', '*', '*', '*', '*', '*', '.', '*'},
{'*', '*', '*', '*', '*', '*', '*', '.', '*'},
{'*', '.', '.', '.', '.', '.', '.', '.', '*'},
{'*', '*', '*', '*', '*', '*', '*', '*', '*'}
};
Solving it with the MazeSolver class:
MazeSolver solver = new MazeSolver(maze);
solver.solve();
The maze array is modified in place. The result:
{
{'*', '*', '*', '*', '*', '*', '*', '*', '*'},
{'*', '0', '+', '+', '*', '+', '*', '+', '*'},
{'*', '*', '*', '+', '*', '+', '*', '+', '*'},
{'*', '-', '-', '-', '-', '+', '*', '+', '*'},
{'*', '*', '*', '*', '*', '*', '*', '+', '*'},
{'*', '*', '*', '*', '*', '*', '*', '+', '*'},
{'*', '+', '+', '+', '+', '+', '+', '+', '*'},
{'*', '*', '*', '*', '*', '*', '*', '*', '*'}
}
The path from the starting position ('0') to the exit is marked with '+'. The dead-ends are marked with '-'.
Dijkstra's algorithm is a graph search algorithm that finds the shortest path between a starting node and all other nodes in a weighted graph. Applied to the maze, it finds the shortest path from the starting position ('0') to the exit.
Folding this into the maze solver takes additional data structures and changes to solveMaze():
solveMaze() to select the minimum-distance node from the priority queue and update the distances of its neighbors.Step-by-step visualization needs a delay between steps and a display of the maze after each modification. In Java, Thread.sleep() pauses execution for a set duration.
This version of MazeSolver adds a visualizeSolve() method:
import java.util.concurrent.TimeUnit;
public class MazeSolver {
// Other class members and methods...
public void visualizeSolve() {
solveMazeVisualization(startRow, startCol);
}
private void solveMazeVisualization(int row, int col) {
if (row < 0 || col < 0 || row >= rows || col >= cols) {
return; // outside of maze boundary
}
if (maze[row][col] == '*' || maze[row][col] == '+' || maze[row][col] == '-') {
return; // wall or visited space
}
if (maze[row][col] == '.') {
maze[row][col] = '+'; // mark as visited
if (row == 0 || col == 0 || row == rows - 1 || col == cols - 1) {
visualizeMaze(); // Display the maze after modification
return; // reached the exit
}
try {
TimeUnit.MILLISECONDS.sleep(500); // Pause for 500 milliseconds (adjust as needed)
} catch (InterruptedException e) {
e.printStackTrace();
}
visualizeMaze(); // Display the maze after modification
solveMazeVisualization(row - 1, col); // up
solveMazeVisualization(row + 1, col); // down
solveMazeVisualization(row, col - 1); // left
solveMazeVisualization(row, col + 1); // right
maze[row][col] = '-'; // mark as dead-end
try {
TimeUnit.MILLISECONDS.sleep(500); // Pause for 500 milliseconds (adjust as needed)
} catch (InterruptedException e) {
e.printStackTrace();
}
visualizeMaze(); // Display the maze after modification
}
}
private void visualizeMaze() {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
System.out.print(maze[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
}
visualizeSolve() pauses for 500 milliseconds via TimeUnit.MILLISECONDS.sleep(500) before and after each recursive call. The duration is adjustable.
visualizeMaze() displays the current state of the maze after each modification. It iterates over the maze array and prints the symbols for walls, visited spaces, and dead-ends.
Loops and multiple solutions each need handling in the algorithm.
Complexity and performance vary with the maze configuration and the approach chosen.
The code above is a basic recursive implementation. It solves mazes correctly, but several optimizations apply:
The trade-offs:
A* search needs a heuristic function that estimates the cost from each node to the goal. For a maze, the Manhattan distance or Euclidean distance between two points is the common choice. A* evaluates nodes on their combined cost and heuristic value and explores the most promising paths first.
This version of MazeSolver uses A* search with the Manhattan distance heuristic:
import java.util.*;
public class MazeSolver {
// Other class members and methods...
public void solveAStar() {
PriorityQueue<Node> openList = new PriorityQueue<>();
Set<Node> closedList = new HashSet<>();
Node startNode = new Node(startRow, startCol, 0);
startNode.setHeuristic(calculateHeuristic(startRow, startCol));
openList.add(startNode);
while (!openList.isEmpty()) {
Node currentNode = openList.poll();
int row = currentNode.getRow();
int col = currentNode.getCol();
if (row == exitRow && col == exitCol) {
reconstructPath(currentNode);
return;
}
closedList.add(currentNode);
exploreNeighbors(row - 1, col, currentNode, openList, closedList); // up
exploreNeighbors(row + 1, col, currentNode, openList, closedList); // down
exploreNeighbors(row, col - 1, currentNode, openList, closedList); // left
exploreNeighbors(row, col + 1, currentNode, openList, closedList); // right
}
System.out.println("No solution found.");
}
private void exploreNeighbors(int row, int col, Node currentNode, PriorityQueue<Node> openList, Set<Node> closedList) {
if (row < 0 || col < 0 || row >= rows || col >= cols) {
return; // outside of maze boundary
}
if (maze[row][col] == '*' || closedList.contains(new Node(row, col))) {
return; // wall or already explored
}
int tentativeGScore = currentNode.getGScore() + 1; // assuming all moves have the same cost
Node neighbor = new Node(row, col, tentativeGScore);
neighbor.setHeuristic(calculateHeuristic(row, col));
neighbor.setParent(currentNode);
if (!openList.contains(neighbor) || tentativeGScore < neighbor.getGScore()) {
openList.remove(neighbor); // remove the neighbor if it's already in the open list with a higher g-score
openList.add(neighbor); // add the neighbor to the open list
}
}
private int calculateHeuristic(int row, int col) {
// Calculate the Manhattan distance heuristic from the current position to the exit position
return Math.abs(exitRow - row) + Math.abs(exitCol - col);
}
private void reconstructPath(Node node) {
List<Node> path = new ArrayList<>();
Node current = node;
while (current != null) {
path.add(0, current);
current = current.getParent();
}
for (Node pathNode : path) {
int row = pathNode.getRow();
int col = pathNode.getCol();
maze[row][col] = '+'; // mark the path
}
}
private static class Node implements Comparable<Node> {
private final int row;
private final int col;
private int gScore;
private int heuristic;
private Node parent;
public Node(int row, int col, int gScore) {
this.row = row;
this.col = col;
this.gScore = gScore;
this.heuristic = 0;
this.parent = null;
}
// Getters and Setters...
@Override
public int compareTo(Node other) {
int fScore = this.gScore + this.heuristic;
int otherFScore = other.gScore + other.heuristic;
return Integer.compare(fScore, otherFScore);
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null || getClass() != obj.getClass()) {
return false;
}
Node other = (Node) obj;
return row == other.row && col == other.col;
}
@Override
public int hashCode() {
return Objects.hash(row, col);
}
}
}
A Node class represents each position in the maze. It holds the row, column, g-score (the cost from the start node), heuristic value, and parent node.
solveAStar() implements the search. A PriorityQueue called openList holds the nodes still to be explored, sorted on total cost (g-score plus heuristic value). The closedList is a set of the nodes already explored.
exploreNeighbors() explores the neighboring nodes of the current node. It calculates the tentative g-score, creates a new Node for the neighbor, and checks whether it belongs in the openList.
calculateHeuristic() calculates the Manhattan distance from a given position to the exit position.
reconstructPath() walks the parent-child relationship stored in each node back from the exit position to the start position, and marks the path in the maze with '+' symbols.
This implementation assumes every move costs the same (1). A maze with different costs for different moves, diagonal moves for instance, needs a different g-score calculation.
The cost system in A* search has two components, the g-score and the heuristic.
The g-score is the cost of reaching a particular node from the starting node along the current path. In a maze it is normally the number of steps taken to reach the node from the starting position. It is updated as the search progresses and nodes are explored.
The heuristic function estimates the cost from a given node to the goal. In a maze, common heuristic functions include the Manhattan distance and the Euclidean distance between two positions. The heuristic guides the search toward nodes that appear closer to the goal.
The total cost of a node is the sum of the g-score and the heuristic value. That total determines priority in the open list, and nodes with lower total costs are explored earlier. The algorithm expands nodes by examining their neighbors and updating g-scores and heuristic values. Combining path cost with estimated cost is what balances exploration of promising paths against optimality, and the objective is the path with the lowest total cost from the starting node to the goal node.
A memoized maze search method, which avoids redundant calculations:
import java.util.*;
public class MazeSolver {
private int rows;
private int cols;
private int startRow;
private int startCol;
private int exitRow;
private int exitCol;
private char[][] maze;
private boolean[][] visited;
private List<String> path;
public MazeSolver(char[][] maze) {
this.maze = maze;
this.rows = maze.length;
this.cols = maze[0].length;
this.visited = new boolean[rows][cols];
this.path = new ArrayList<>();
}
public List<String> solveMemoized() {
// Clear the visited state and path
for (int i = 0; i < rows; i++) {
Arrays.fill(visited[i], false);
}
path.clear();
// Call the memoized search method from the starting position
memoizedSearch(startRow, startCol);
return path;
}
private boolean memoizedSearch(int row, int col) {
// Base case: if the current position is outside the maze boundaries or is a wall
if (row < 0 || row >= rows || col < 0 || col >= cols || maze[row][col] == '*') {
return false;
}
// Base case: if the current position is the exit position
if (row == exitRow && col == exitCol) {
path.add(getPositionString(row, col));
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;
// Recursive exploration in all four directions
if (memoizedSearch(row - 1, col)) { // up
path.add(getPositionString(row, col));
return true;
}
if (memoizedSearch(row + 1, col)) { // down
path.add(getPositionString(row, col));
return true;
}
if (memoizedSearch(row, col - 1)) { // left
path.add(getPositionString(row, col));
return true;
}
if (memoizedSearch(row, col + 1)) { // right
path.add(getPositionString(row, col));
return true;
}
return false;
}
private String getPositionString(int row, int col) {
return "(" + row + ", " + col + ")";
}
}
solveMemoized() is the entry point. It resets the visited state, clears the path list, then calls memoizedSearch() to start from the starting position.
memoizedSearch() is a recursive function that explores the maze depth-first. It checks the base cases, reaching the exit or hitting a wall, then explores the neighboring positions recursively.
The memoization is the visited array, which tracks visited positions. Before exploring a position, the method checks whether it has already been visited.
When a successful path to the exit is found, the positions are added to the path list in reverse order, from the exit back to the starting position.
This implementation assumes a rectangular grid represented by a 2D character array, where '*' is a wall and other characters are open spaces or the start and exit positions. A different maze representation needs adjustments.
Memoization and regular depth-first search (DFS) differ on four points.
In maze solving, memoization caches the results of visiting specific positions so that previously explored paths are not revisited. Regular DFS explores all possible paths exhaustively without storing previous results, potentially revisiting positions and recomputing paths. Memoization trades additional space complexity for improved time complexity.
A multi-threaded maze search method using Java's ExecutorService and Callable interface:
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.*;
public class MazeSolver {
private char[][] maze;
private int rows;
private int cols;
private int startRow;
private int startCol;
private int exitRow;
private int exitCol;
private List<String> path;
private ExecutorService executorService;
public MazeSolver(char[][] maze) {
this.maze = maze;
this.rows = maze.length;
this.cols = maze[0].length;
this.path = new ArrayList<>();
this.executorService = Executors.newCachedThreadPool();
}
public List<String> solveMultiThreaded() {
// Clear the path
path.clear();
// Submit the initial search task
Future<Boolean> future = executorService.submit(new MazeSearchTask(startRow, startCol));
try {
// Wait for the result of the search task
boolean found = future.get();
if (found) {
// Path found, return the result
return path;
} else {
// No path found
return new ArrayList<>();
}
} catch (InterruptedException | ExecutionException e) {
// Exception occurred, handle accordingly
e.printStackTrace();
return new ArrayList<>();
} finally {
// Shutdown the executor service
executorService.shutdown();
}
}
private class MazeSearchTask implements Callable<Boolean> {
private int row;
private int col;
public MazeSearchTask(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public Boolean call() throws Exception {
// Base cases
if (row < 0 || row >= rows || col < 0 || col >= cols || maze[row][col] == '*') {
return false;
}
if (row == exitRow && col == exitCol) {
path.add(getPositionString(row, col));
return true;
}
// Recursive exploration in all four directions
List<Future<Boolean>> results = new ArrayList<>();
results.add(executorService.submit(new MazeSearchTask(row - 1, col))); // up
results.add(executorService.submit(new MazeSearchTask(row + 1, col))); // down
results.add(executorService.submit(new MazeSearchTask(row, col - 1))); // left
results.add(executorService.submit(new MazeSearchTask(row, col + 1))); // right
for (Future<Boolean> result : results) {
if (result.get()) {
path.add(getPositionString(row, col));
return true;
}
}
return false;
}
}
private String getPositionString(int row, int col) {
return "(" + row + ", " + col + ")";
}
}
A MazeSearchTask class implements the Callable interface. Each task represents the search for a specific position in the maze. solveMultiThreaded() submits the initial search task to the ExecutorService and waits for the result.
MazeSearchTask explores the maze recursively, as the single-threaded version does. But instead of invoking the method recursively, it submits a new MazeSearchTask to the executor service for each neighboring position, so multiple search tasks run concurrently in different threads.
The Future<Boolean> objects hold the results of each search task, retrieved by calling get() on each Future. The method returns as soon as a path to the exit is found.
The example calls Executors.newCachedThreadPool(), which creates an executor service whose thread pool adjusts its size to the number of submitted tasks.
MazeSearchTask class implements the Callable interface.MazeSearchTask instance represents the search for a specific position in the maze.MazeSearchTask is submitted to the ExecutorService for each neighboring position.Future objects, which report whether a path to the exit has been found.Each thread explores a portion of the search space independently. Thread creation, synchronization, and context switching add overhead. How much multi-threading helps depends on the size of the maze, the number of available cores, and the complexity of the search space.
Thread generated with ChatGPT [https://chat.openai.com] and downloaded with Botrush [https://botrush.io]