ソリティアという伝統的な１人用パズルゲームがある。
32個のビー玉を盤に配置し、ビー玉を縦か横に一つジャンプさせて空いたところに置く。ジャンプされたビー玉は台から取り除く。
この手続きを繰り返して最後の１つになったらクリア。最後の１つが真ん中で残ったら最高。
これがなかなか難しい。頑張ったけど、一度もできなかった。
そこで、再帰を使って解を探索してみることにする。
まず、初期状態をnumpy の2次元配列でコーディング。
[crayon]
import numpy as np
# 初期状態 0:穴なし、1:玉なし、 2:玉あり
S_INIT = [‘000000000’,
‘000222000’,
‘000222000’,
‘022222220’,
‘022212220’,
‘022222220’,
‘000222000’,
‘000222000’,
‘000000000’]
N = len(S_INIT) # S_INIT の1辺の長さ = 9
# S_INIT をnumpyの2次元配列s0に変換
s0 = np.zeros((N, N), dtype=np.uint8)
for j, s in enumerate(S_INIT):
for i in range(len(s)):
s0[j, i] = int(s[i])
print(s0)
[/crayon]
出力は、
[crayon]
[[0 0 0 0 0 0 0 0 0]
[0 0 0 2 2 2 0 0 0]
[0 0 0 2 2 2 0 0 0]
[0 2 2 2 2 2 2 2 0]
[0 2 2 2 1 2 2 2 0]
[0 2 2 2 2 2 2 2 0]
[0 0 0 2 2 2 0 0 0]
[0 0 0 2 2 2 0 0 0]
[0 0 0 0 0 0 0 0 0]]
[/crayon]
このコーディングを図で出力する関数 draw_state(state) を作る。
[crayon]
from PIL import Image, ImageDraw
UNIT = 10 # 穴の間隔
BOARD_W = UNIT * N # 画像の大きさ
BOARD_PAD = 2 # 穴の間隔
COL_BACK = (100, 100, 100) # 盤の色
COL_BALL = (255, 100, 0) # ボールの色
COL_OUT = (0, 0, 0) # 穴の色
FONT_SIZE = 12
FONT_NAME = “C:\Windows\Fonts\meiryob.ttc”
FONT_COL = (200, 200, 200)
FONT = ImageFont.truetype(FONT_NAME, FONT_SIZE)
#LINE_COL = (200, 200, 200)
LINE_COL = (0, 0, 0)
LINE_WIDTH = 2
def draw_state(state, text):
img = Image.new(‘RGB’, (BOARD_W, BOARD_W), COL_BACK)
draw = ImageDraw.Draw(img)
draw.text((12, 10), text, font=FONT, fill=FONT_COL)
for i in range(N):
for j in range(N):
col = None
if state[i, j] > 0:
x0 = j * UNIT + BOARD_PAD
x1 = (j + 1) * UNIT – BOARD_PAD
y0 = i * UNIT + BOARD_PAD
y1 = (i + 1) * UNIT – BOARD_PAD
if state[i, j] == 1:
col = COL_OUT
else:
col = COL_BALL
draw.ellipse((x0, y0, x1, y1), fill=col, outline=COL_OUT)
return img, BOARD_W
# test
img, w = draw_state(s0, ’01’)
print(w)
img.save(’01one.png’)
img
[/crayon]
次に、上の盤面を32個並べて表示する関数draw_32states(states)を作成。
[crayon]
from PIL import ImageFont
W_N = 4 # ボードを並べる横の数
H_N = 8 # ボードを並べる縦の数
ALL_W = BOARD_W * W_N # 全体図の横の長さ
ALL_H = BOARD_W * H_N # 全体図の縦の長さ
def draw_32states(states):
img_back = Image.new(‘RGB’, (ALL_W, ALL_H), COL_BACK)
i = 0
for ih in range(H_N):
for iw in range(W_N):
img, _ = draw_state(states[i], ‘%02d’ % (i+1))
img_back.paste(img, (iw * BOARD_W, ih * BOARD_W))
i += 1
if i == len(states):
return img_back
return img_back
# test
states = []
for i in range(32):
states.append(s0)
img_back = draw_32states(states)
img_back.save(’02_32.png’)
img_back
[/crayon]
そして、ある状態sを入力すると、ありうる次の状態s1をすべて出力する関数cal_next(state)を作る。
[crayon]
def cal_next(state):
dirc=np.array([[1, 0], [-1, 0], [0, 1], [0, -1]]) # dx, dy
next_state=[]
for iy in range(N):
for ix in range(N):
if state[iy, ix] == 2:
for d in range(4):
if state[iy + dirc[d, 1], ix + dirc[d, 0]] == 2:
if state[iy + 2 * dirc[d, 1], ix + 2 * dirc[d, 0]] == 1:
s = state.copy()
s[iy, ix] = 1
s[iy + 1 * dirc[d, 1], ix + 1 * dirc[d, 0]] = 1
s[iy + 2 * dirc[d, 1], ix + 2 * dirc[d, 0]] = 2
next_state.append(s)
return next_state
# test
next_state = cal_next(s0)
img = draw_32states(next_state)
img.save(’03_next_s.png’)
img
[/crayon]
これでお膳立ては終わり。いよいよ再帰で解を探索する。
以下のsolve_solitaire(states)は、statesの次の状態state2を計算し、そのすべてに対してsolve_solitaire(state2)を実行する。
state2が何もない場合には、関数はそれ以上呼ばない。また、state2の残りの玉が1つになったらパズルは解けたことになるので、画像を保存する。
解の数がどれくらいあるかわからないので、とりあえず、解を2つ見つけたら強制的に終了するようにした。
[crayon]
import sys
MAX_SOLUTIONS = 2
def solve_solitaire(states):
global CNT, CC
“””
次の状態 state2 を計算し、
残りが1つだったら画像保存
“””
N_t = 1
state = states[-1].copy()
state2 = cal_next(state)
if len(state2) == 0:
# 手詰まり
return
else:
if np.sum(state2[0] == 2) > N_t:
# まだ残っている
for i in range(len(state2)):
ss = states.copy()
s2 = state2[i].copy()
ss.append(s2)
CC += 1
solve_solitaire(ss)
else:
# クリア
for i in range(len(state2)):
s2 = state2[i].copy()
ss = states.copy()
ss.append(s2)
img = draw_32states(ss)
img.save(‘%03d.png’ % CNT)
CNT += 1
if CNT >= MAX_SOLUTIONS:
sys.exit()
return
# test
global CNT, CC
CNT = 0
CC = 0
solve_solitaire([s0])
[/crayon]
なんと、3秒くらで2つの解が出力された！
僕がたどり着けなかった解が一瞬で導き出されて、、少し複雑な心境だ。
再帰すごい！という話でした。