[Pythonプログラミング]スライドパズルを解くアルゴリズムを比較する : 乙Py先生のプログラミング教室

今回は4x4のスライドパズルを解く
アルゴリズムの解説です

解説動画はこちら

スライドパズルを解くアルゴリズム

こんな感じのスライドパズルを

1 2 3 4

5 6 7 8

9 0 10 11

13 14 15 12

プログラムで解いていきます

今回は4つのアルゴリズムを用いて
スライドパズルを解いていきます

1. 幅優先探索 (BFS)

2. A* アルゴリズム

3. IDA* (Iterative Deepening A*)

4. モンテカルロ探索

各アルゴリズムの詳細

1. 幅優先探索 (BFS)

特徴: 全ての状態を探索してから
次の深さへ進む解を見つけるときは最短手数を保証

利点: 最短経路を必ず見つける

欠点: メモリ消費量が非常に大きい
4x4スライドパズルのような小規模な問題では問題ない

2. A* アルゴリズム

特徴: 幅優先探索の効率化版状態の評価にヒューリスティック関数を使用

利点: ヒューリスティック関数が良い場合、効率的に最適解を発見可能

欠点: メモリ消費が高く、ヒューリスティックが不適切だと探索が非効率になる

3. IDA* (反復深化 A*)

特徴: 深さ優先探索をA* ベースにしたアルゴリズムで
閾値を段階的に増やす

利点: メモリ使用量が少なく、大規模な問題に対応しやすい

欠点: 反復のため、特定の状態を何度も評価するため
時間効率はA*に劣ることがある

4. モンテカルロ探索

特徴: ランダムなシミュレーションで解を探す非決定的アルゴリズム

利点: 実装が簡単で、初期状態から短時間で結果を得られることが多い

欠点: 最適解を保証できず、試行回数による品質のばらつきが大きい

適用シナリオ

幅優先探索: 状態空間が小さく、メモリ制限が問題にならない場合

A*: 高精度のヒューリスティック関数を使い、効率的に最適解を探したい場合

IDA*: メモリ効率を優先しつつ、最適解を求める場合

モンテカルロ探索: 厳密な最適性が不要で、迅速におおよその解を得たい場合

スライドパズルを解くベースのコード

ここからはスライドパズルを解くベースのコードです
先に実行しておいてください

from collections import deque
import heapq
import random
import time

# 目標状態
GOAL_STATE = [
  [ 1,  2,  3,  4],
  [ 5,  6,  7,  8],
  [ 9, 10, 11, 12],
  [13, 14, 15,  0],
]

# 空白の移動方向
DIRECTIONS = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def is_solvable(state):
    """スライドパズルが解けるかを判定"""
    rows, cols = len(state), len(state[0])
    
    # グリッドを1次元リストに変換（空白は無視）
    flat_list = [tile for row in state for tile in row if tile != 0]

    # 転倒数を計算
    inversions = sum(
        1 for i in range(len(flat_list)) for j in range(i + 1, len(flat_list)) if flat_list[i] > flat_list[j]
    )

    # 空白タイルの行（0インデックスで計算）
    blank_row = next(i for i, row in enumerate(state) if 0 in row)
    blank_row_from_bottom = rows - blank_row

    # 判定条件 (4x4の場合)
    if rows % 2 == 0:
        if inversions % 2 == 0 and blank_row_from_bottom % 2 == 1:
            return True
        elif inversions % 2 == 1 and blank_row_from_bottom % 2 == 0:
            return True
    else:
        if inversions % 2 == 0:
            return True
    return False

def find_blank(state):
  """空白セルの位置を見つける"""
  for i, row in enumerate(state):
      for j, val in enumerate(row):
          if val == 0:
              return i, j

def print_state(state):
    """
    パズルの状態をきれいに表示する
    :param state: 現在の状態 (2次元リスト)
    """
    for row in state:
        print(" ".join(f"{num:2}" if num != 0 else "  " for num in row))
    print()

def apply_solution(initial_state, solution):
    """
    初期状態に solution を適用し、各ステップ後の状態をプリント
    :param initial_state: 初期状態 (2次元リスト)
    :param solution: 解 (空白タイルの新しい位置を示すリスト)
    """
    state = [row[:] for row in initial_state]  # 初期状態をコピー
    rows, cols = len(state), len(state[0])

    # 空白タイル (0) の位置を見つける
    blank_pos = next((r, c) for r in range(rows) for c in range(cols) if state[r][c] == 0)

    print("Initial state:")
    print_state(state)

    # 解を適用
    for step, new_pos in enumerate(solution, start=1):
        # 現在の空白位置
        old_r, old_c = blank_pos
        new_r, new_c = new_pos

        # タイルをスワップ
        state[old_r][old_c], state[new_r][new_c] = state[new_r][new_c], state[old_r][old_c]

        # 更新された空白位置
        blank_pos = new_pos

        # 各ステップ後の状態をプリント
        print(f"After step {step}:")
        print_state(state)

これで準備は整いました
ここからはアルゴリズムの詳細を解説します。

幅優先探索 (BFS)

初期状態をキューに追加

キューから状態を1つ取り出し、目標状態と比較

解なら終了

探索済みならスキップ

空白セルを上下左右に動かして新しい状態を生成

新しい状態をキューに追加

キューが空になるか解が見つかるまで繰り返す

def bfs_solve(initial_state):
  """幅優先探索でスライドパズルを解く"""
  queue = deque([(initial_state, [], find_blank(initial_state))]) # 幅優先探索のキュー
  visited = set() # すでに探索済みの状態を記録する集合

  while queue:
      # state : 現在のパズルの状態
      # path: 現在までの移動履歴
      state, path, (blank_row, blank_col) = queue.popleft()
      if state == GOAL_STATE:
          return path  # 解が見つかったら手順を返す

      state_tuple = tuple(tuple(row) for row in state)
      if state_tuple in visited:
          continue
      visited.add(state_tuple)

      # DIRECTIONS : 空白セルを動かす4方向（上下左右）を表すリスト
      for dr, dc in DIRECTIONS:
          new_row, new_col = blank_row + dr, blank_col + dc
          if 0 <= new_row < 4 and 0 <= new_col < 4:
              new_state = [row[:] for row in state]
              new_state[blank_row][blank_col], new_state[new_row][new_col] = new_state[new_row][new_col], new_state[blank_row][blank_col]
              queue.append((new_state, path + [(new_row, new_col)], (new_row, new_col)))

A* アルゴリズム

初期状態をヒープに追加

ヒープから評価値が最小の状態を取り出し、目標状態と比較

解なら移動履歴を返す

探索済みならスキップ

空白セルを上下左右に動かして新しい状態を生成

新しい状態をヒューリスティックで評価し、ヒープに追加

ヒープが空になるか解が見つかるまで繰り返す

# パズルの現在の状態と目標状態（GOAL_STATE）の間の「マンハッタン距離」を計算
def manhattan_distance(state):
    """マンハッタン距離を計算"""
    distance = 0
    for i in range(4):
        for j in range(4):
            val = state[i][j] # 現在の状態を参照
            if val != 0:
                target_row, target_col = divmod(val - 1, 4)
                distance += abs(target_row - i) + abs(target_col - j) # 現在位置（i, j）との差分
    return distance

def astar_solve(initial_state):
    """A*アルゴリズムでスライドパズルを解く"""
    open_set = [] # ヒープ（優先度付きキュー）で管理する探索候補リスト
    heapq.heappush(open_set, (manhattan_distance(initial_state), 0, initial_state, []))
    visited = set() # 探索済みの状態を管理する集合

    while open_set:
        _, cost, state, path = heapq.heappop(open_set) # 現在の状態を state、その手数を cost、移動履歴を path に代入
        if state == GOAL_STATE:
            return path  # 解が見つかったら手順を返す

        state_tuple = tuple(tuple(row) for row in state)
        if state_tuple in visited:
            continue
        visited.add(state_tuple)

        blank_row, blank_col = find_blank(state)
        for dr, dc in DIRECTIONS:
            new_row, new_col = blank_row + dr, blank_col + dc
            if 0 <= new_row < 4 and 0 <= new_col < 4:
                new_state = [row[:] for row in state]
                new_state[blank_row][blank_col], new_state[new_row][new_col] = new_state[new_row][new_col], new_state[blank_row][blank_col]
                heapq.heappush(open_set, (cost + manhattan_distance(new_state), cost + 1, new_state, path + [(new_row, new_col)]))

IDA*アルゴリズム

初期状態の評価値（threshold）を計算

現在のしきい値内で深さ優先探索（DFS）を実行

解が見つかった場合は手順を返す

見つからない場合は次のしきい値を計算

次のしきい値で探索を再開

解が見つかるか探索が終了するまで繰り返す

def ida_star_solve(initial_state):
    """IDA*アルゴリズムでスライドパズルを解く"""
    def dfs(state, g, threshold, path, blank_pos):
        # 深さ優先探索を行い、指定されたコスト制限（threshold）内で解を探索
        f = g + manhattan_distance(state) # g : 現在までの手数（コスト）
        if f > threshold: # threshold :現在の探索制限（評価値の上限）
            return f, None
        if state == GOAL_STATE:
            return f, path # path : 現在までの移動履歴
        min_threshold = float('inf')
        blank_row, blank_col = blank_pos # blank_pos : 空白セルの位置
        for dr, dc in DIRECTIONS:
            new_row, new_col = blank_row + dr, blank_col + dc
            if 0 <= new_row < 4 and 0 <= new_col < 4:
                new_state = [row[:] for row in state]
                new_state[blank_row][blank_col], new_state[new_row][new_col] = new_state[new_row][new_col], new_state[blank_row][blank_col]
                if len(path) > 0 and path[-1] == (new_row, new_col):
                    continue  # 直前の状態に戻るのを防ぐ
                t, result = dfs(new_state, g + 1, threshold, path + [(new_row, new_col)], (new_row, new_col))
                if result is not None:
                    return t, result
                min_threshold = min(min_threshold, t)
        return min_threshold, None

    threshold = manhattan_distance(initial_state) 
    blank_pos = find_blank(initial_state)
    path = []
    while True:
        t, result = dfs(initial_state, 0, threshold, path, blank_pos)
        if result is not None:
            return result
        if t == float('inf'):
            return None
        threshold = t

モンテカルロ探索

ランダムな移動を繰り返して解を探索

指定された最大試行回数（max_iterations）内に
目標状態（GOAL_STATE）に到達すれば
その移動手順（path）を返す

解が見つからない場合は None を返す

def monte_carlo_solve(initial_state, max_iterations=1000):
    """モンテカルロ探索でスライドパズルを解く"""
    state = [row[:] for row in initial_state] # 初期状態
    path = [] # 空白セル（0）の移動履歴を記録するリスト
    blank_row, blank_col = find_blank(state)

	# 最大 max_iterations 回、以下の操作を繰り返す
	# 現在の状態（state）が目標状態（GOAL_STATE）と一致した場合、成功として移動履歴（path）を返す
    for _ in range(max_iterations):
        if state == GOAL_STATE:
            return path  # 解が見つかったら終了

        # ランダムに移動
        valid_moves = [(dr, dc) for dr, dc in DIRECTIONS if 0 <= blank_row + dr < 4 and 0 <= blank_col + dc < 4]
        dr, dc = random.choice(valid_moves)
        new_row, new_col = blank_row + dr, blank_col + dc
        state[blank_row][blank_col], state[new_row][new_col] = state[new_row][new_col], state[blank_row][blank_col]
        path.append((new_row, new_col))
        blank_row, blank_col = new_row, new_col

    return None  # 最大試行回数を超えても解けなかった場合

4つのアルゴリズムでパズルを解く

solution が解けた状態です
コメントアウトして
アルゴリズムの違いを見る事ができます。

# 初期状態
initial_state = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 0, 11],
  [13, 14, 15, 12],
]

if is_solvable(initial_state):
    #solution = bfs_solve(initial_state)
    #solution = astar_solve(initial_state)
    #solution = ida_star_solve(initial_state)
    solution = monte_carlo_solve(initial_state)

    # 解を適用して各ステップ後の状態を表示
    apply_solution(initial_state, solution)
else:
    print("This puzzle is unsolvable.")

Initial state:

1 2 3 4

5 6 7 8

9 10 11

13 14 15 12

After step 1:

1 2 3 4

5 6 8

9 10 7 11

13 14 15 12

After step 2:

1 2 3 4

5 6 7 8

9 10 11

13 14 15 12

After step 3:

1 2 3 4

5 6 7 8

9 10 11

13 14 15 12

After step 4:

1 2 3 4

5 6 7 8

9 10 11 12

13 14 15

まとめ

今回はスライドパズルを解く
4つのアルゴリズムを紹介しました

それぞれに特徴があり
まとめるとこんな感じです。

アルゴリズム	計算量	メモリ消費	解の最適性
幅優先探索 (BFS)	\(O(b^d)\), b:分岐数, d:深さ	高い	最適解を保証
A\* アルゴリズム	\(O(b^d)\)	高い	最適解を保証
IDA (反復深化 A)	\(O(b^d)\)	低い	最適解を保証
モンテカルロ探索	探索回数に依存	低い	保証されない