JavaによるBFSを使用した8パズル問題の解決方法

import java.util.*;
public class EightPuzzleSolver {
    private static final int[][] GOAL_STATE = {{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 State {
        private int[][] board;
        private int zeroRow;
        private int zeroCol;

        public State(int[][] board, int zeroRow, int zeroCol) {
            this.board = board;
            this.zeroRow = zeroRow;
            this.zeroCol = zeroCol;
        }

        public boolean isGoalState() {
            return Arrays.deepEquals(board, GOAL_STATE);
        }

        public List<State> getNextStates() {
            List<State> nextStates = new ArrayList<>();

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

                if (isValid(newRow, newCol)) {
                    int[][] newBoard = copyBoard();
                    swapTiles(newBoard, zeroRow, zeroCol, newRow, newCol);
                    nextStates.add(new State(newBoard, newRow, newCol));
                }
            }

            return nextStates;
        }

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

        private int[][] copyBoard() {
            int[][] newBoard = new int[3][3];

            for (int i = 0; i < 3; i++) {
                newBoard[i] = Arrays.copyOf(board[i], 3);
            }

            return newBoard;
        }

        private void swapTiles(int[][] board, int row1, int col1, int row2, int col2) {
            int temp = board[row1][col1];
            board[row1][col1] = board[row2][col2];
            board[row2][col2] = temp;
        }
    }

    public static List<State> solve(int[][] initialBoard) {
        List<State> solution = new ArrayList<>();
        Queue<State> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();

      // 初期状態をキューに追加
        State initialState = new State(initialBoard, 0, 0);
        queue.add(initialState);

        while (!queue.isEmpty()) {
            State currentState = queue.poll();

            if (currentState.isGoalState()) {
                // 目標状態に到達した場合、解を返す
                while (currentState != null) {
                    solution.add(currentState);
                    currentState = currentState.parent;
                }
                Collections.reverse(solution);
                break;
            }

            for (State nextState : currentState.getNextStates()) {
                String nextStateString = Arrays.deepToString(nextState.board);
                if (!visited.contains(nextStateString)) {
                    queue.add(nextState);
                    visited.add(nextStateString);
                }
            }
        }

        return solution;
    }

    public static void main(String[] args) {
        int[][] initialBoard = {{1, 2, 3}, {4, 0, 6}, {7, 5, 8}};
        List<State> solution = solve(initialBoard);

        if (solution.isEmpty()) {
            System.out.println("解が見つかりませんでした。");
        } else {
            for (State state : solution) {
                printBoard(state.board);
                System.out.println();
            }
        }
    }

    private static void printBoard(int[][] board) {
        for (int[] row : board) {
            for (int tile : row) {
                System.out.print(tile + " ");
            }
            System.out.println();
        }
    }
}

メインメソッドでは、初期ボードを設定し、solveメソッドを呼び出して解を取得します。解が見つかった場合は、各ステップのボードの状態を表示します。

このコードを実行すると、8パズル問題の解が表示されます。もし解が見つからない場合は、「解が見つかりませんでした。」と表示されます。