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


解説動画はこちら



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






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

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

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)

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

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)))

# パズルの現在の状態と目標状態（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)]))

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

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.")

まとめ

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

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

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

アルゴリズムのよって
計算量やメモリの効率が異なってくるので
状況に応じた使い分けが必要になる事があります。

色々なアルゴリズムで
試してみてください。

それでは。

タグ ：

#プログラミング

#Python

#スライドパズル

#探索アルゴリズム

本日は暇な時の時間潰しにぴったりな
方形を数えるプログラムについてです


解説動画はこちら




問題

次の図形の中に正方形または長方形は
幾つあるでしょうか?
(黒塗りの部分が図形で 5x3 マスです)







探索プログラムの考え方


今回は四角形を探索するプログラムです

図形を黒を1 白を0でデータ化したのち
黒塗りの部分で作られる方形が
幾つあるのかを左上から順番に数えていきます。

起点を左上とし、そこから縦と横に
1マスずつ伸ばして数えていきます。

途中白(0)があったら探索を抜けて次に進みます。

こんな感じで探していきます。




方形を数えるコード

コードはこんな感じになります。

import matplotlib.pyplot as plt
import numpy as np

# 指定された左上(top, left)を基準に黒い長方形を数える
def count_black_rectangles_from_top_left(grid, top, left):
    # 左上が黒でなければカウントしない
    if grid[top][left] != 1:
        return 0  
    rows, cols, count = len(grid), len(grid[0]), 0
    
    # 指定された左上から長方形を探索
    for bottom in range(top, rows):
        for right in range(left, cols):
            # 長方形内がすべて黒かを確認
            if all(grid[i][j] == 1 for i in range(top, bottom + 1) for j in range(left, right + 1)):
                count += 1
            else:
                # 白いセルが見つかったらその方向は探索不要
                break  
    return count

# グリッド内のすべての黒い長方形を数える
def count_black_rectangles(grid):
    rows, cols, total_count = len(grid), len(grid[0]), 0
    for top in range(rows):
        for left in range(cols):
            total_count += count_black_rectangles_from_top_left(grid, top, left)
    return total_count

# グリッドのプロット
def plot_grid(grid):
    plt.figure(figsize=(6, 4))
    plt.imshow(np.array(grid), cmap="binary", interpolation="nearest")
    plt.title("Grid Visualization")
    plt.axis("off")
    plt.show()

# ブロックのカウントの実行

# グリッドの初期配置
grid = [
    [1, 1, 1, 0, 1],
    [1, 0, 1, 0, 1],
    [1, 1, 1, 1, 0],
]
plot_grid(grid)
result = count_black_rectangles(grid)
print(f"Number of black rectangles: {result}")

ぜひGoogle Colabなどにコピペして
試してみてください

もっと大きな16x16でやると
こうなります。

# ブロックのカウントの実行

# グリッドの初期配置
grid = [
    [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0],
]

plot_grid(grid)
result = count_black_rectangles(grid)
print(f"Number of black rectangles: {result}")

何個あるのかは数えてみてくださいね

こういった探索プログラムは
アルゴリズムを考える基本にもなり
プログラミングの上達にも役立ちますね!!!


今回は暇つぶしにぴったりな
方形を数えるプログラムについてでした

それでは

タグ ：

#プログラミング

#Python

#探索

#正方形

#長方形

今回は画像に隠しメッセージを仕込める技術
ステガノグラフィーのご紹介です。


解説動画はこちら



ステガノグラフィーとは














音声ファイルや動画ファイルにも同様の手法が使われ


元画像はこんな感じです。






画像にメッセージを埋め込むコードサンプル

from PIL import Image

def encode_image(image_path, secret_message, output_path):
    # 画像を開く
    image = Image.open(image_path)
    encoded_image = image.copy()

    # メッセージをバイナリに変換
    binary_message = ''.join(format(ord(char), '08b') for char in secret_message) + '11111111'  # 終了ビット
    data_index = 0

    # 画像のピクセルを走査
    for y in range(encoded_image.height):
        for x in range(encoded_image.width):
            pixel = list(encoded_image.getpixel((x, y)))
            for i in range(3):  # RGBの各成分
                if data_index < len(binary_message):
                    pixel[i] = (pixel[i] & ~1) | int(binary_message[data_index])  # 最下位ビットを変更
                    data_index += 1
            encoded_image.putpixel((x, y), tuple(pixel))
            if data_index >= len(binary_message):
                break
        if data_index >= len(binary_message):
            break

    encoded_image.save(output_path)

# 使用例
input_img_path = "画像のパス"
input_message = "埋め込むメッセージ"
output_img_path = "出力後のパス"
encode_image(input_img_path, input_message, output_img_path)

実行するとメッセージを埋め込んだ画像が生成されます。

元の画像と比較すると




差分はほとんどわからないですね！！


画像からメッセージを取り出すコードサンプル

from PIL import Image

# バイナリメッセージを8ビットごとに分割して文字に変換
def make_message(binary_message):
    message = ''
    for i in range(0, len(binary_message), 8):
        byte = binary_message[i:i+8]
        if byte == '11111111':  # 終了ビットを検出
            break
        message += chr(int(byte, 2))
    return message

def decode_image(image_path):
    image = Image.open(image_path)
    binary_message = ''

    # 画像のピクセルを走査
    for y in range(image.height):
        for x in range(image.width):
            pixel = image.getpixel((x, y))
            for i in range(3):  # RGBの各成分
                binary_message += str(pixel[i] & 1)  # 最下位ビットを取得

    return make_message(binary_message)

# 使用例
decoded_message = decode_image('output_image.png')
print("Decoded message:", decoded_message)

Decoded message: Hello Otupy

メッセージが復元されました。




最後に

こちらの画像にはメッセージを埋め込んでいるので
ダウンロードして解読してみてくださいね






今回はステガノグラフィーをご紹介しました
画像などに隠しメッセージを残せるので

暗号のように秘匿したいやりとりで
使うこともできたりして
なかなか面白い技術です。

いろいろ遊んでみてみてくださいね
それでは

タグ ：

#python

#プログラミング

#ステガノグラフィー