8-puzzle Problem with A* and RBFS

EightPuzzleAnalysis.java

import java.util.*;
import java.time.Instant;
import java.time.Duration;

public class EightPuzzleAnalysis {
    public static void main(String[] args) {
        int[][] initialState = {
                { 7, 2, 4 },
                { 5, 0, 6 },
                { 8, 3, 1 }
        };

        PuzzleSolver solver = new PuzzleSolver();
        solver.runAnalysis(initialState);
    }
}

class PuzzleState implements Comparable<PuzzleState> {
    private final int[][] state;
    private final int cost;
    private final PuzzleState parent;
    private final double fValue;

    public PuzzleState(int[][] state, PuzzleState parent, int cost, double fValue) {
        this.state = new int[3][3];
        for (int i = 0; i < 3; i++) {
            System.arraycopy(state[i], 0, this.state[i], 0, 3);
        }
        this.parent = parent;
        this.cost = cost;
        this.fValue = fValue;
    }

    public int[][] getState() {
        return state;
    }

    public int getCost() {
        return cost;
    }

    public PuzzleState getParent() {
        return parent;
    }

    public double getFValue() {
        return fValue;
    }

    public int[] getBlankPosition() {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (state[i][j] == 0) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[] { 0, 0 };
    }

    public List<PuzzleState> getSuccessors(PuzzleSolver solver, double parentFValue) {
        List<PuzzleState> successors = new ArrayList<>();
        int[] blank = getBlankPosition();
        int[][] moves = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

        for (int[] move : moves) {
            int newRow = blank[0] + move[0];
            int newCol = blank[1] + move[1];

            if (newRow >= 0 && newRow < 3 && newCol >= 0 && newCol < 3) {
                int[][] newState = new int[3][3];
                for (int i = 0; i < 3; i++) {
                    System.arraycopy(state[i], 0, newState[i], 0, 3);
                }
                newState[blank[0]][blank[1]] = newState[newRow][newCol];
                newState[newRow][newCol] = 0;

                double newFValue = Math.max(
                        cost + 1 + solver.getCurrentHeuristic().apply(newState),
                        parentFValue);
                successors.add(new PuzzleState(newState, this, cost + 1, newFValue));
            }
        }
        return successors;
    }

    @Override
    public int compareTo(PuzzleState other) {
        return Double.compare(this.fValue, other.fValue);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o)
            return true;
        if (o == null || getClass() != o.getClass())
            return false;
        PuzzleState that = (PuzzleState) o;
        return Arrays.deepEquals(state, that.state);
    }

    @Override
    public int hashCode() {
        return Arrays.deepHashCode(state);
    }
}

class SearchResult {
    public final List<int[][]> path;
    public final long nodesExplored;
    public final double timeInSeconds;

    public SearchResult(List<int[][]> path, long nodesExplored, double timeInSeconds) {
        this.path = path;
        this.nodesExplored = nodesExplored;
        this.timeInSeconds = timeInSeconds;
    }
}

class PuzzleSolver {
    private final int[][] goalState = {
            { 1, 2, 3 },
            { 4, 5, 6 },
            { 7, 8, 0 }
    };
    private Function<int[][], Integer> currentHeuristic;

    interface Function<T, R> {
        R apply(T t);
    }

    public Function<int[][], Integer> getCurrentHeuristic() {
        return currentHeuristic;
    }

    private int manhattanDistance(int[][] state) {
        int distance = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (state[i][j] != 0) {
                    int value = state[i][j] - 1;
                    int goalRow = value / 3;
                    int goalCol = value % 3;
                    distance += Math.abs(i - goalRow) + Math.abs(j - goalCol);
                }
            }
        }
        return distance;
    }

    private int misplacedTiles(int[][] state) {
        int count = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (state[i][j] != 0 && state[i][j] != goalState[i][j]) {
                    count++;
                }
            }
        }
        return count;
    }

    private int sqrtManhattan(int[][] state) {
        return (int) Math.sqrt(manhattanDistance(state));
    }

    private int maxHeuristic(int[][] state) {
        return Math.max(manhattanDistance(state), misplacedTiles(state));
    }

    public SearchResult a_star(int[][] initialState, Function<int[][], Integer> heuristic) {
        this.currentHeuristic = heuristic;
        Instant startTime = Instant.now();
        int nodesExplored = 0;

        PuzzleState initialNode = new PuzzleState(
                initialState, null, 0,
                heuristic.apply(initialState));

        PriorityQueue<PuzzleState> frontier = new PriorityQueue<>();
        Set<PuzzleState> explored = new HashSet<>();
        frontier.add(initialNode);

        while (!frontier.isEmpty()) {
            PuzzleState current = frontier.poll();
            nodesExplored++;

            if (Arrays.deepEquals(current.getState(), goalState)) {
                return new SearchResult(
                        getPath(current),
                        nodesExplored,
                        Duration.between(startTime, Instant.now()).toMillis() / 1000.0);
            }

            explored.add(current);

            for (PuzzleState successor : current.getSuccessors(this, current.getFValue())) {
                if (!explored.contains(successor)) {
                    frontier.add(successor);
                }
            }
        }
        return null;
    }

    public SearchResult rbfs(int[][] initialState, Function<int[][], Integer> heuristic) {
        this.currentHeuristic = heuristic;
        Instant startTime = Instant.now();
        long[] nodesExplored = { 0 };

        PuzzleState initialNode = new PuzzleState(
                initialState, null, 0,
                heuristic.apply(initialState));

        RBFSResult result = rbfsSearch(initialNode, Double.POSITIVE_INFINITY, nodesExplored);

        if (result.state != null) {
            return new SearchResult(
                    getPath(result.state),
                    nodesExplored[0],
                    Duration.between(startTime, Instant.now()).toMillis() / 1000.0);
        }
        return null;
    }

    private static class RBFSResult {
        PuzzleState state;
        double fLimit;

        RBFSResult(PuzzleState state, double fLimit) {
            this.state = state;
            this.fLimit = fLimit;
        }
    }

    private RBFSResult rbfsSearch(PuzzleState node, double fLimit, long[] nodesExplored) {
        nodesExplored[0]++;

        if (Arrays.deepEquals(node.getState(), goalState)) {
            return new RBFSResult(node, node.getFValue());
        }

        List<PuzzleState> successors = node.getSuccessors(this, node.getFValue());
        if (successors.isEmpty()) {
            return new RBFSResult(null, Double.POSITIVE_INFINITY);
        }

        double[] fValues = new double[successors.size()];
        for (int i = 0; i < successors.size(); i++) {
            fValues[i] = successors.get(i).getFValue();
        }

        while (true) {
            int bestIndex = 0;
            for (int i = 1; i < successors.size(); i++) {
                if (fValues[i] < fValues[bestIndex]) {
                    bestIndex = i;
                }
            }

            if (fValues[bestIndex] > fLimit) {
                return new RBFSResult(null, fValues[bestIndex]);
            }

            int altIndex = 0;
            for (int i = 0; i < successors.size(); i++) {
                if (i != bestIndex && fValues[i] < fValues[altIndex]) {
                    altIndex = i;
                }
            }

            RBFSResult result = rbfsSearch(
                    successors.get(bestIndex),
                    Math.min(fLimit, fValues[altIndex]),
                    nodesExplored);

            if (result.state != null) {
                return result;
            }

            fValues[bestIndex] = result.fLimit;
        }
    }

    private List<int[][]> getPath(PuzzleState state) {
        List<int[][]> path = new ArrayList<>();
        PuzzleState current = state;
        while (current != null) {
            path.add(current.getState());
            current = current.getParent();
        }
        Collections.reverse(path);
        return path;
    }

    public void runAnalysis(int[][] initialState) {
        Map<String, Function<int[][], Integer>> heuristics = new LinkedHashMap<>();
        heuristics.put("Manhattan Distance", this::manhattanDistance);
        heuristics.put("Misplaced Tiles", this::misplacedTiles);
        heuristics.put("Sqrt Manhattan", this::sqrtManhattan);
        heuristics.put("Max Heuristic", this::maxHeuristic);

        System.out.println("\nAnalysis Results:");
        System.out.println("================");

        for (String algorithm : Arrays.asList("A*", "RBFS")) {
            System.out.println("\n" + algorithm + " Algorithm:");
            System.out.println("-".repeat(60));
            System.out.printf("%-20s %-15s %-10s %s%n",
                    "Heuristic", "Nodes Explored", "Time (s)", "Path Length");
            System.out.println("-".repeat(60));

            for (Map.Entry<String, Function<int[][], Integer>> entry : heuristics.entrySet()) {
                SearchResult result = algorithm.equals("A*")
                        ? a_star(initialState, entry.getValue())
                        : rbfs(initialState, entry.getValue());

                if (result != null) {
                    System.out.printf("%-20s %-15d %-10.4f %d%n",
                            entry.getKey(),
                            result.nodesExplored,
                            result.timeInSeconds,
                            result.path.size() - 1);
                }
            }
        }
    }
}