6パズルの解法:BFSマトリックス

コード例1: Python

from collections import deque
def solve_puzzle(start_state, goal_state):
    queue = deque([(start_state, [])])
    visited = set([start_state])
    while queue:
        current_state, path = queue.popleft()
        if current_state == goal_state:
            return path
        for next_state, move in get_possible_moves(current_state):
            if next_state not in visited:
                queue.append((next_state, path + [move]))
                visited.add(next_state)
    return None
def get_possible_moves(state):
    # 状態stateで可能な移動を返す関数
    # 実装は省略
# 使用例
start_state = [[2, 8, 3], [1, 6, 4], [7, 0, 5]]
goal_state = [[1, 2, 3], [8, 0, 4], [7, 6, 5]]
solution = solve_puzzle(start_state, goal_state)
if solution:
    print("解が見つかりました！")
    print("解の手順:", solution)
else:
    print("解が見つかりませんでした。")

コード例2: Java

import java.util.*;
class PuzzleState {
    int[][] state;
    List<String> path;
    public PuzzleState(int[][] state, List<String> path) {
        this.state = state;
        this.path = path;
    }
}
public class PuzzleSolver {
    public static List<String> solvePuzzle(int[][] startState, int[][] goalState) {
        Queue<PuzzleState> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(new PuzzleState(startState, new ArrayList<>()));
        while (!queue.isEmpty()) {
            PuzzleState currentState = queue.poll();
            if (Arrays.deepEquals(currentState.state, goalState)) {
                return currentState.path;
            }
            for (PuzzleState nextState : getPossibleMoves(currentState.state)) {
                String nextStateString = Arrays.deepToString(nextState.state);
                if (!visited.contains(nextStateString)) {
                    queue.offer(new PuzzleState(nextState.state, new ArrayList<>(currentState.path)));
                    visited.add(nextStateString);
                }
            }
        }
        return null;
    }
    public static List<PuzzleState> getPossibleMoves(int[][] state) {
        // 状態stateで可能な移動を返すメソッド
        // 実装は省略
        return possibleMoves;
    }
    public static void main(String[] args) {
        int[][] startState = {{2, 8, 3}, {1, 6, 4}, {7, 0, 5}};
        int[][] goalState = {{1, 2, 3}, {8, 0, 4}, {7, 6, 5}};
        List<String> solution = solvePuzzle(startState, goalState);
        if (solution != null) {
            System.out.println("解が見つかりました！");
            System.out.println("解の手順: " + solution);
        } else {
            System.out.println("解が見つかりませんでした。");
        }
    }
}

上記のPythonとJavaのコード例は、BFSアルゴリズムを使用して6パズルを解く方法を示しています。幅優先探索は、最短経路を見つけるための一般的なアルゴリズムです。このアルゴリズムでは、キューを使用して次に探索する状態を管理し、訪れた状態を記録します。

この記事では、他の方法やプログラミング言語についても解説する予定ですが、これらのコード例を使ってBFSを使用した6パズルの解法を詳しく説明しました。