### Instruction:
Create a Java program that generates random mazes using Prim's algorithm, and solves them using A* search algorithm. Display the generated maze and solution path in the console.


### Response:

Here's a Java program that generates random mazes using Prim's algorithm and solves them using the A* search algorithm. The generated maze and solution path are displayed in the console.

```java
import java.util.*;

public class MazeGenerator {
    private static final char WALL = '#';
    private static final char PATH = ' ';
    private static final char START = 'S';
    private static final char END = 'E';
    private static final char SOLUTION_PATH = '.';

    public static void main(String[] args) {
        int width = 25;
        int height = 25;

        char[][] maze = generateMaze(width, height);
        printMaze(maze);

        System.out.println("\nSolution:");
        solveMaze(maze);
        printMaze(maze);
    }

    private static char[][] generateMaze(int width, int height) {
        char[][] maze = new char[height][width];

        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                maze[y][x] = WALL;
            }
        }

        Random rand = new Random();
        int startX = rand.nextInt(width / 2) * 2 + 1;
        int startY = rand.nextInt(height / 2) * 2 + 1;
        maze[startY][startX] = START;

        List<int[]> frontier = new ArrayList<>();
        addNeighborsToFrontier(maze, startX, startY, frontier);

        while (!frontier.isEmpty()) {
            int[] current = frontier.remove(rand.nextInt(frontier.size()));
            int x = current[0];
            int y = current[1];

            if (maze[y][x] == WALL) {
                int count = 0;
                int dx = 0;
                int dy = 0;

                if (maze[y - 1][x] == PATH) {
                    count++;
                    dy = 1;
                }
                if (maze[y + 1][x] == PATH) {
                    count++;
                    dy = -1;
                }
                if (maze[y][x - 1] == PATH) {
                    count++;
                    dx = 1;
                }
                if (maze[y][x + 1] == PATH) {
                    count++;
                    dx = -1;
                }

                if (count == 1) {
                    maze[y][x] = PATH;
                    maze[y + dy][x + dx] = PATH;

                    addNeighborsToFrontier(maze, x, y, frontier);
                }
            }
        }

        int endX = rand.nextInt(width / 2) * 2 + 1;
        int endY = rand.nextInt(height / 2) * 2 + 1;
        maze[endY][endX] = END;

        return maze;
    }

    private static void addNeighborsToFrontier(char[][] maze, int x, int y, List<int[]> frontier) {
        for (int[] dir : new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
            int newX = x + dir[0] * 2;
            int newY = y + dir[1] * 2;

            if (newX >= 0 && newX < maze[0].length && newY >= 0 && newY < maze.length && maze[newY][newX] == WALL) {
                frontier.add(new int[]{newX, newY});
            }
        }
    }

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

    private static void solveMaze(char[][] maze) {
        int startX = 0;
        int startY = 0;

        outer:
        for (int y = 0; y < maze.length; y++) {
            for (int x = 0; x < maze[y].length; x++) {
                if (maze[y][x] == START) {
                    startX = x;
                    startY = y;
                    break outer;
                }
            }
        }

        PriorityQueue<Node> openSet = new PriorityQueue<>(Comparator.comparingInt(a -> a.f));
        Node startNode = new Node(startX, startY, null);
        openSet.add(startNode);

        while (!openSet.isEmpty()) {
            Node current = openSet.poll();

            if (maze[current.y][current.x] == END) {
                while (current.parent != null) {
                    maze[current.y][current.x] = SOLUTION_PATH;
                    current = current.parent;
                }
                return;
            }

            for (int[] dir : new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
                int newX = current.x + dir[0];
                int newY = current.y + dir[1];

                if (newX >= 0 && newX < maze[0].length && newY >= 0 && newY < maze.length &&
                        (maze[newY][newX] == PATH || maze[newY][newX] == END)) {
                    Node neighbor = new Node(newX, newY, current);
                    openSet.removeIf(n -> n.x == newX && n.y == newY && n.f > neighbor.f);
                    openSet.add(neighbor);
                }
            }
        }
    }

    private static class Node {
        int x;
        int y;
        Node parent;

        int g; // cost from start to this node
        int h; // heuristic cost from this node to end
        int f; // total cost (g + h)

        public Node(int x, int y, Node parent) {
            this.x = x;
            this.y = y;
            this.parent = parent;

            if (parent != null) {
                this.g = parent.g + 1;
            }
            this.h = Math.abs(x - parent.x) + Math.abs(y - parent.y);
            this.f = this.g + this.h;
        }
    }
}
```

You can run the program and see the generated maze and solution path in the console. The maze is represented by '#' for walls, 'S' for the starting point, 'E' for the ending point, and '.' for the solution path.