Вот пример решения задачи из 8 головоломок с использованием алгоритма поиска в ширину (BFS) на Java:

import java.util.*;
public class EightPuzzleBFS {
    private static final int[][] goalState = {{1, 2, 3}, {4, 5, 6}, {7, 8, 0}};
    private static final int[][] moves = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    private static class Node {
        private int[][] state;
        private int zeroRow;
        private int zeroCol;
        private Node parent;

        public Node(int[][] state, int zeroRow, int zeroCol, Node parent) {
            this.state = state;
            this.zeroRow = zeroRow;
            this.zeroCol = zeroCol;
            this.parent = parent;
        }

        public boolean isGoalState() {
            return Arrays.deepEquals(state, goalState);
        }
    }

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

    private static void solvePuzzle(int[][] initialState) {
        Node initialNode = new Node(initialState, 1, 1, null);
        Queue<Node> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        queue.add(initialNode);
        visited.add(Arrays.deepToString(initialState));

        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();

            if (currentNode.isGoalState()) {
                printSolution(currentNode);
                return;
            }

            for (int[] move : moves) {
                int newRow = currentNode.zeroRow + move[0];
                int newCol = currentNode.zeroCol + move[1];

                if (isValidMove(newRow, newCol)) {
                    int[][] newState = cloneState(currentNode.state);
                    swap(newState, currentNode.zeroRow, currentNode.zeroCol, newRow, newCol);

                    if (!visited.contains(Arrays.deepToString(newState))) {
                        Node newNode = new Node(newState, newRow, newCol, currentNode);
                        queue.add(newNode);
                        visited.add(Arrays.deepToString(newState));
                    }
                }
            }
        }

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

    private static boolean isValidMove(int row, int col) {
        return row >= 0 && row < 3 && col >= 0 && col < 3;
    }

    private static int[][] cloneState(int[][] state) {
        int[][] newState = new int[3][3];

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                newState[i][j] = state[i][j];
            }
        }

        return newState;
    }

    private static void swap(int[][] state, int row1, int col1, int row2, int col2) {
        int temp = state[row1][col1];
        state[row1][col1] = state[row2][col2];
        state[row2][col2] = temp;
    }

    private static void printSolution(Node node) {
        List<Node> path = new ArrayList<>();
        Node currentNode = node;

        while (currentNode != null) {
            path.add(currentNode);
            currentNode = currentNode.parent;
        }

        for (int i = path.size() - 1; i >= 0; i--) {
            printState(path.get(i).state);
            System.out.println();
        }
    }

    private static void printState(int[][] state) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                System.out.print(state[i][j] + " ");
            }
            System.out.println();
        }
    }
}

Эта реализация использует класс Nodeдля представления состояния головоломки и связанной с ней информации, такой как текущее состояние, положение пустой ячейки (ноля) и родительского узла. Метод solvePuzzleвыполняет алгоритм BFS для поиска решения. Он использует очередь для хранения узлов, которые необходимо исследовать, и набор для отслеживания посещенных состояний, чтобы избежать их повторного посещения.

Метод isValidMoveпроверяет, допустимо ли перемещение в пределах границ головоломки. Метод cloneStateсоздает глубокую копию состояния головоломки. Метод swapменяет местами две ячейки в состоянии головоломки. Метод printSolutionпечатает путь решения, перемещая родительские узлы из целевого состояния в исходное.