今回はレイトン教授シリーズに出てきた
パズルゲームを解くプログラムについてです。


解説動画はこちら


 




謎解きと称した
たくさんの小ゲームで構成されており
これを解いてクリアしていく

パズルゲームなどもかなりたくさん有る

今回はその中でも代表的な
スライドパズル系のパズルを解くものです。





こういったパズルを特には
次のような考え方が重要になってきます。


これらを用いて解くコードを
考えてみました。

Google colabで実行できるようになっています。
日本語表示ように先にこれをインストールしておいてください。

pip install japanize_matplotlib

ナイトツアーを解くコード


colab上ではwidgetsでスライダーを用いて
画像を変更できるようにしています。

import matplotlib.pyplot as plt
import numpy as np
import ipywidgets as widgets
from IPython.display import display

# ナイトの移動可能な8つの方向
dx = [2, 1, -1, -2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

def is_valid_move(x, y, board):
    return 0 <= x < N and 0 <= y < N and board[x][y] == -1

def solveKnightTour(x, y, move_count, board):
    if move_count == N * N:
        return True
    for i in range(8):
        next_x = x + dx[i]
        next_y = y + dy[i]
        if is_valid_move(next_x, next_y, board):
            board[next_x][next_y] = move_count
            if solveKnightTour(next_x, next_y, move_count + 1, board):
                return True
            board[next_x][next_y] = -1
    return False

def knightTour(board):
    if solveKnightTour(0, 0, 1, board):
        return board
    else:
        print("解が見つかりませんでした")
        return None

# ステップごとのボード状態を画像として保存
def make_img(N):
    img_data = []
    for step in range(N * N):
        fig, ax = plt.subplots(figsize=(8, 8))
        ax.set_xticks(np.arange(N+1)-0.5, minor=True)
        ax.set_yticks(np.arange(N+1)-0.5, minor=True)
        ax.grid(which="minor", color="black", linestyle='-', linewidth=2)
        ax.set_xticks(np.arange(N), minor=False)
        ax.set_yticks(np.arange(N), minor=False)
        ax.grid(which="major", color="black", linestyle='-', linewidth=0)
        
        for i in range(N):
            for j in range(N):
                if board[i][j] <= step:
                    color = 'pink' if board[i][j] == step else ('bisque' if (i + j) % 2 == 0 else 'saddlebrown')
                    ax.text(j, i, str(board[i][j]), ha='center', va='center', fontsize=12)
                    ax.add_patch(plt.Rectangle((j-0.5, i-0.5), 1, 1, fill=True, color=color))
        
        ax.set_xlim(-0.5, N-0.5)
        ax.set_ylim(N-0.5, -0.5)
        ax.set_xticklabels([])
        ax.set_yticklabels([])
        
        fig.canvas.draw()
        img_data.append(np.frombuffer(fig.canvas.buffer_rgba(), dtype=np.uint8).reshape(fig.canvas.get_width_height()[::-1] + (4,)))
        plt.close(fig)
    return img_data

N = 8
board = [[-1 for _ in range(N)] for _ in range(N)]
board[0][0] = 0 # スタート位置

# 解読スタート
board = knightTour(board)
img_data = make_img(N)

# スライダーウィジェットの作成
step_selector = widgets.IntSlider(min=0, max=N*N-1, step=1, description='Step:')

def update_board(step):
    plt.figure(figsize=(8, 8))
    plt.imshow(img_data[step])
    plt.axis('off')
    plt.show()

# インタラクティブなプロットの作成と表示
interactive_plot = widgets.interactive(update_board, step=step_selector)
display(interactive_plot)

同じ色のブロックはスライドできます。
互いに重ね合わせは出来ず、出口までスライドさせます。
これをデータに定義して解くコードになります。

ここでは

from collections import deque
import copy
import japanize_matplotlib
import matplotlib.pyplot as plt
import matplotlib.patches as patches
import io
from IPython.display import display
import ipywidgets as widgets
from PIL import Image

# ボードのサイズを定義
BOARD_WIDTH = 4
BOARD_HEIGHT = 5

# 駒の初期配置を定義
INITIAL_STATE = [
    ['父', '娘', '娘', '母'],
    ['父', '娘', '娘', '母'],
    ['下', '番', '番', '小'],
    ['下', '中', '', ''],
    ['', '', '', '']
]

# 駒のサイズを定義
PIECE_SIZES = {
    '娘': (2, 2),
    '父': (1, 2),
    '母': (1, 2),
    '番': (2, 1),
    '小': (1, 1),
    '中': (1, 1),
    '下': (2, 1)
}

# 駒の色を定義
PIECE_COLORS = {
    '娘': 'red',
    '父': 'blue',
    '母': 'green',
    '番': 'purple',
    '小': 'orange',
    '中': 'gray',
    '下': 'brown'
}

DIRECTIONS = {
    'up': (-1, 0),
    'down': (1, 0),
    'left': (0, -1),
    'right': (0, 1)
}

### 画像を描画

def draw_board(state):
    fig, ax = plt.subplots()
    ax.set_xlim(0, BOARD_WIDTH)
    ax.set_ylim(0, BOARD_HEIGHT)
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_aspect('equal')

    for x in range(BOARD_HEIGHT):
        for y in range(BOARD_WIDTH):
            piece = state[x][y]
            if piece:
                width, height = 1, 1
                color = PIECE_COLORS.get(piece, 'gray')
                rect = patches.Rectangle((y, BOARD_HEIGHT - x - 1), width, height, linewidth=1, edgecolor='black', facecolor=color)
                ax.add_patch(rect)
                cx, cy = y + width / 2, BOARD_HEIGHT - x - 1 + height / 2
                ax.text(cx, cy, piece, color='white', ha='center', va='center', fontsize=12, fontweight='bold')

    # 画像をバイトデータとして保存
    buf = io.BytesIO()
    plt.savefig(buf, format='png')
    buf.seek(0)
    plt.close(fig)
    return buf

def generate_images(solution):
    images = []
    for state in solution:
        buf = draw_board(state)
        image = Image.open(buf)
        images.append(image)
    return images

### パズルを解く

def is_goal(state):
    """ゴール状態のチェック"""
    # 例として、特定の位置に特定の駒があるかをチェック
    return state[4][1] == '娘' and state[4][2] == '娘'

def can_move(state, piece, direction):
    """駒が指定の方向に動けるかをチェック"""
    dx, dy = DIRECTIONS[direction]
    for i in range(BOARD_HEIGHT):
        for j in range(BOARD_WIDTH):
            if state[i][j] == piece:
                ni, nj = i + dx, j + dy
                if ni < 0 or ni >= BOARD_HEIGHT or nj < 0 or nj >= BOARD_WIDTH or (state[ni][nj] != '' and state[ni][nj] != piece):
                    return False
    return True

def move_piece(state, piece, direction):
    """駒を指定の方向に動かす"""
    dx, dy = DIRECTIONS[direction]
    new_state = copy.deepcopy(state)
    positions = [(i, j) for i in range(BOARD_HEIGHT) for j in range(BOARD_WIDTH) if state[i][j] == piece]
    for i, j in positions:
        new_state[i][j] = ''
    for i, j in positions:
        new_state[i + dx][j + dy] = piece
    return new_state

def solve(initial_state):
    """幅優先探索でパズルを解く"""
    queue = deque([(initial_state, [])])
    visited = set()
    visited.add(tuple(tuple(row) for row in initial_state))

    while queue:
        current_state, path = queue.popleft()

        if is_goal(current_state):
            return path + [current_state]

        for piece in PIECE_SIZES.keys():
            for direction in DIRECTIONS.keys():
                if can_move(current_state, piece, direction):
                    new_state = move_piece(current_state, piece, direction)
                    state_tuple = tuple(tuple(row) for row in new_state)
                    if state_tuple not in visited:
                        visited.add(state_tuple)
                        queue.append((new_state, path + [current_state]))

    return None

# パズルを解く
solution_path = solve(INITIAL_STATE)

# solution_pathから各ステップの状態を取得
if solution_path:
    solution = solution_path
else:
    solution = []

# 画像データを生成
images = generate_images(solution)

# 画像を表示する関数
def show_image(index):
    display(images[index])

# スライダーウィジェットの作成
slider = widgets.IntSlider(min=0, max=len(images)-1, step=1, description='Step:')
output = widgets.Output()
def on_slider_change(change):
    with output:
        output.clear_output(wait=True)
        show_image(change['new'])

slider.observe(on_slider_change, names='value')

# ウィジェットの表示
with output:
    show_image(0)
display(slider, output)

箱入り娘と違って動かせないブロックが
存在する部分の違いがあります。
これも先ほどと同様、幅優先探索(BFS)で解きます。

from collections import deque
import copy
import matplotlib.pyplot as plt
import matplotlib.patches as patches
import io
from IPython.display import display
import ipywidgets as widgets
from PIL import Image

# ボードのサイズ
BOARD_WIDTH = 6
BOARD_HEIGHT = 6

# 駒の初期配置
INITIAL_STATE = [
    ['0', '0', '10', '0', '0', '0'],
    ['', '1', '1', '7', '5', ''],
    ['2', '2', '9', '9', '5', '0'],
    ['0', '6', '9', '9', '3', '3'],
    ['', '6', '8', '4', '4', ''],
    ['0', '0', '0', '', '0', '0']
]

# 駒のサイズ
PIECE_SIZES = {
    '1': (2, 1),
    '2': (2, 1),
    '3': (2, 1),
    '4': (2, 1),
    '5': (1, 2),
    '6': (1, 2),
    '7': (1, 1),
    '8': (1, 1),
    '9': (2, 2),
    '10': (1, 1),
}

DIRECTIONS = {
    'up': (-1, 0),
    'down': (1, 0),
    'left': (0, -1),
    'right': (0, 1)
}

# 駒の色を定義
PIECE_COLORS = {
    "0": 'gray',
    "1": 'green',
    "2": 'blue',
    "3": 'green',
    "4": 'blue',
    "5": 'magenta',
    "6": 'magenta',
    "7": 'purple',
    "8": 'purple',
    "9": 'yellow',
    "10": 'red'
}

### 画像を描画

def draw_board(state):
    fig, ax = plt.subplots()
    ax.set_xlim(0, BOARD_WIDTH)
    ax.set_ylim(0, BOARD_HEIGHT)
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_aspect('equal')

    for x in range(BOARD_HEIGHT):
        for y in range(BOARD_WIDTH):
            piece = state[x][y]
            if piece:
                width, height = 1, 1
                color = PIECE_COLORS.get(piece, 'gray')
                rect = patches.Rectangle((y, BOARD_HEIGHT - x - 1), width, height, linewidth=1, edgecolor='black', facecolor=color)
                ax.add_patch(rect)
                cx, cy = y + width / 2, BOARD_HEIGHT - x - 1 + height / 2
                ax.text(cx, cy, piece, color='white', ha='center', va='center', fontsize=12, fontweight='bold')

    # 画像をバイトデータとして保存
    buf = io.BytesIO()
    plt.savefig(buf, format='png')
    buf.seek(0)
    plt.close(fig)
    return buf

def generate_images(solution):
    images = []
    for state in solution:
        buf = draw_board(state)
        image = Image.open(buf)
        images.append(image)
    return images

def is_goal(state):
    """ゴール状態のチェック"""
    return state[5][3] == '10'

def can_move(state, piece, direction):
    """駒が指定の方向に動けるかをチェック"""
    dx, dy = DIRECTIONS[direction]
    for i in range(BOARD_HEIGHT):
        for j in range(BOARD_WIDTH):
            if state[i][j] == piece:
                ni, nj = i + dx, j + dy
                if ni < 0 or ni >= BOARD_HEIGHT or nj < 0 or nj >= BOARD_WIDTH or (state[ni][nj] != '' and state[ni][nj] != piece):
                    return False
    return True

def move_piece(state, piece, direction):
    """駒を指定の方向に動かす"""
    dx, dy = DIRECTIONS[direction]
    new_state = copy.deepcopy(state)
    positions = [(i, j) for i in range(BOARD_HEIGHT) for j in range(BOARD_WIDTH) if state[i][j] == piece]
    for i, j in positions:
        new_state[i][j] = ''
    for i, j in positions:
        new_state[i + dx][j + dy] = piece
    return new_state

def solve(initial_state):
    """幅優先探索でパズルを解く"""
    queue = deque([(initial_state, [])])
    visited = set()
    visited.add(tuple(tuple(row) for row in initial_state))

    while queue:
        current_state, path = queue.popleft()

        if is_goal(current_state):
            return path + [current_state]

        for piece in PIECE_SIZES.keys():
            if piece == '0':
                continue
            for direction in DIRECTIONS.keys():
                if can_move(current_state, piece, direction):
                    new_state = move_piece(current_state, piece, direction)
                    state_tuple = tuple(tuple(row) for row in new_state)
                    if state_tuple not in visited:
                        visited.add(state_tuple)
                        queue.append((new_state, path + [current_state]))

    return None

# パズルを解く
solution_path = solve(INITIAL_STATE)

# solution_pathから各ステップの状態を取得
if solution_path:
    solution = solution_path
else:
    solution = []

#画像データを生成する関数を再利用して描画（この関数はユーザーが提供するものと仮定）
images = generate_images(solution)

#画像を表示する関数（この関数はユーザーが提供するものと仮定）
def show_image(index):
   display(images[index])

#スライダーウィジェットの作成
slider = widgets.IntSlider(min=0, max=len(images)-1, step=1, description='Step:')
output = widgets.Output()

def on_slider_change(change):
   with output:
       output.clear_output(wait=True)
       show_image(change['new'])

slider.observe(on_slider_change, names='value')

#初期表示
with output:
   show_image(0)

#ウィジェットの表示
display(slider, output)

動画内では1枚ずつ解く過程が見られるので
答えを見たい方は最後のおまけを見てみてください。


おわりに

レイトン教授の最後の方のパズルはかなり難しく
人力ではなかなか解けずに、諦めた方も多いのではないでしょうか

そんなパズルもPythonプログラムであれば
解く事ができるコードも作成できるので
パズルゲームに困ったら
プログラミングの力を借りると良いかもしれません。

それでは。

タグ ：

#Python

#プログラミング

#パズルゲーム

#レイトン教授

#DFS探索

#バックトラッキング