今回はレイトン教授シリーズに出てきた
パズルゲームを解くプログラムについてです。
解説動画はこちら
レベルファイブから発売された
ニンテンドーDSのアドベンチャーゲームシリーズ
謎解きと称した
たくさんの小ゲームで構成されており
これを解いてクリアしていく
パズルゲームなどもかなりたくさん有る
今回はその中でも代表的な
スライドパズル系のパズルを解くものです。
さあ、すべてのマス目を旅してみよう(8aがスタート)
こういったパズルを特には
次のような考え方が重要になってきます。
・データ構造:
バックトラッキング: 再帰呼び出しやスタックを使って探索を進める
幅優先探索(BFS): キューを使って探索を進める
これらを用いて解くコードを
考えてみました。
Google colabで実行できるようになっています。
日本語表示ように先にこれをインストールしておいてください。
ナイトツアーを解くコード
colab上ではwidgetsでスライダーを用いて
画像を変更できるようにしています。
これは少し実問題と内容が違います。
下記のような構造のパズルを解くものです。
同じ色のブロックはスライドできます。
互いに重ね合わせは出来ず、出口までスライドさせます。
これをデータに定義して解くコードになります。
ここでは
赤い玉を出口(一番下のマス目)まで持っていけるかな？
箱入り娘と違って動かせないブロックが
存在する部分の違いがあります。
これも先ほどと同様、幅優先探索(BFS)で解きます。
動画内では1枚ずつ解く過程が見られるので
答えを見たい方は最後のおまけを見てみてください。
おわりに
レイトン教授の最後の方のパズルはかなり難しく
人力ではなかなか解けずに、諦めた方も多いのではないでしょうか
そんなパズルもPythonプログラムであれば
解く事ができるコードも作成できるので
パズルゲームに困ったら
プログラミングの力を借りると良いかもしれません。
それでは。
パズルゲームを解くプログラムについてです。
解説動画はこちら
レイトン教授シリーズとは
レベルファイブから発売された
ニンテンドーDSのアドベンチャーゲームシリーズ
謎解きと称した
たくさんの小ゲームで構成されており
これを解いてクリアしていく
パズルゲームなどもかなりたくさん有る
今回はその中でも代表的な
スライドパズル系のパズルを解くものです。
1.ナイトツアー
チェスのナイトの駒で旅をしよう
ナイトは将棋の桂馬のように、2つ先のマス目の左右どちらかに移動できる
ただし、上下左右、どちらの方向にも移動可能である
ただし、1度訪れたマス目には2度と入ることができない
さあ、すべてのマス目を旅してみよう(8aがスタート)
こういったパズルを特には
次のような考え方が重要になってきます。
・探索の深さと幅:
バックトラッキング: 深さ優先探索（DFS）の一種で
ある経路を可能な限り深く探索する
ある経路を可能な限り深く探索する
幅優先探索(BFS): 各レベルのノードを順に探索し
より広く浅く探索する
より広く浅く探索する
・データ構造:
バックトラッキング: 再帰呼び出しやスタックを使って探索を進める
幅優先探索(BFS): キューを使って探索を進める
これらを用いて解くコードを
考えてみました。
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)
2.箱入り娘
じゃまするブロックをスライドさせて
赤い大きなブロックを右側の出口から出してほしい
これは少し実問題と内容が違います。
下記のような構造のパズルを解くものです。
同じ色のブロックはスライドできます。
互いに重ね合わせは出来ず、出口までスライドさせます。
これをデータに定義して解くコードになります。
ここでは
幅優先探索(BFS): キューを使って探索を進める
を用いて探索を行います。
を用いて探索を行います。
キュー : データを先入れ先出しのリスト構造で保持するもの
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)
3.玉を出せ
赤い玉を出口(一番下のマス目)まで持っていけるかな？
じゃまなブロックをうまく動かして道を作ろう。
(灰色のブロックは動かせない)
箱入り娘と違って動かせないブロックが
存在する部分の違いがあります。
これも先ほどと同様、幅優先探索(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プログラムであれば
解く事ができるコードも作成できるので
パズルゲームに困ったら
プログラミングの力を借りると良いかもしれません。
それでは。
コメントする