問題の説明
「フリップ・イット (Flip It)」は芦ヶ原伸之氏が考案されたパズルで、すべての駒を裏返しにするのが目的です。今回はリバーシの駒を使うことにします。次の図を見てください。
フリップ・イットのルールは簡単です。ある駒はほかの駒を跳び越して空き場所へ移動することができます。空き場所の隣にある駒は、跳び越す駒がないので移動できません。このとき、跳び越された駒は裏返しにされますが、跳んだ駒はそのままです。図では 5 の位置にある駒が 0 へ跳び、それから 2 の駒が 5 へ跳んだ場合を示しています。このあと 0 -> 2, 5 -> 0 と跳ぶと、すべての駒を白にすることができます。
参考文献 12 には 1 行 5 列 の問題があります。今回のパズル「フリップ・イット・スター」は駒の配置を六芒星の形にしたバージョンです。それでは問題です。
図では空き場所を □ で表しています。ルールは「フリップ・イット」と同じで、駒は直線に沿ってほかの駒を跳び越すことができます。途中で曲がって跳び越すことは許されません。すべての駒を白にする最短手順を求めてください。
●幅優先探索による解法
まずは単純な幅優先探索でプログラムを作りましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。最初に駒の置き方が何通りあるか数えましょう。これは空き場所の配置から考えた方が簡単です。盤面の大きさは 12 なので、空き場所の配置は 12 通りあります。残りは黒か白のどちらかなので、駒の配置は 2 11 = 2048 通りあります。したがって、全体では 12 * 2048 = 24576 通りになります。けっこう大きな数になりますね。そこで、同一局面のチェックには Python の辞書を使うことにします。
次は大域変数を定義します。
リスト : 大域変数の定義
# 盤面の大きさ
SIZE = 12
# 駒
S = 0
B = 1
W = 2
# 直線
line = [
[0, 2, 5, 7], [0, 3, 6, 10], [7, 8, 9, 10],
[1, 2, 3, 4], [1, 5, 8, 11], [4, 6, 9, 11]
]
# 駒の跳び先表 (直線の番号, 駒の位置)
jump_table = [
[(0, 5), (0, 7), (1, 6), (1, 10)], # 0
[(3, 3), (3, 4), (4, 8), (4, 11)], # 1
[(0, 7), (3, 4)], # 2
[(1, 10), (3, 1)], # 3
[(3, 1), (3, 2), (5, 9), (5, 11)], # 4
[(0, 0), (4, 11)], # 5
[(1, 0), (5, 11)], # 6
[(0, 0), (0, 2), (2, 9), (2, 10)], # 7
[(2, 10), (4, 1)], # 8
[(2, 7), (5, 4)], # 9
[(1, 0), (1, 3), (2, 7), (2, 8)], # 10
[(4, 1), (4, 5), (5, 4), (5, 6)], # 11
]
盤面は一次元配列 (Python のタプル) で表します。盤面の位置と配列の添字の対応は、上図のように定義します。すると、6 本の直線はリスト line で表すことができます。ここで、line に格納される番号は昇順に並んでいることに注意してください。
駒の移動は跳び先表を定義すると簡単です。jump_table は空き場所を基準にして、タプル (直線の番号, 移動する駒の位置) を格納しています。たとえば、空き場所が 2 番目であれば、直線 0 の 7 番目にある駒、直線 3 の 4 番目にある駒を動かすことがでます。
駒を動かす関数 move_piece() は次のようになります。
リスト : 駒を動かす
def move_piece(b, l, p1, p2):
xs = list(b)
# 駒と空き場所の交換
xs[p1], xs[p2] = xs[p2], xs[p1]
# 順番のチェック
if p2 < p1: p1, p2 = p2, p1
# 駒の裏返し
for i in range(4):
p3 = line[l][i]
if p1 < p3 < p2:
if xs[p3] == B:
xs[p3] = W
else:
xs[p3] = B
return tuple(xs)
引数 b が盤面を表すタプル、 l が直線の番号、p1 と p2 が動かす駒の位置と空き場所の位置です。空き場所と駒の位置は p1 と p2 のどちらでもかまいません。最初にタプルをリスト xs に変換して、p1 と p2 にある要素を交換します。次に駒を裏返しにしますが、ここで配列 line に格納されている番号が昇順に並んでいることを利用します。p1 < p2 になるように値を入れ替えて、p1 と p2 の間にある駒を裏返しにします。最後に、xs をタプルに変換して返します。
あとは単純な幅優先探索で最短手順を求めるだけです。次のリストを見てください。
リスト : 幅優先探索による解法
def bfs(start):
queue = [(start, -1, start.index(S))]
check = {}
check[start] = True
rc = 0
while rc < len(queue):
b, _, s = queue[rc]
if b.count(W) == SIZE - 1:
print_moves(rc, queue)
return
for l, p in jump_table[s]:
newb = move_piece(b, l, p, s)
if newb in check: continue
queue.append((newb, rc, p))
check[newb] = True
rc += 1
def solver_bfs():
start = [B] * SIZE
start[0] = S
bfs(tuple(start))
関数 bfs() の引数 start はスタートの盤面を表すタプルです。リスト queue をキューとして使います。要素は、盤面、1 手前の盤面の添字、空き場所の位置を格納したタプルです。check は Python の辞書で初期化して、check[start] を True にセットします。変数 rc はキューのリードカウンタとして使います。
while ループで、キューにデータがある間は探索を続けます。queue からデータを一つ取り出して、盤面と空き場所の位置を変数 b と s にセットします。b.count(W) が SIZE - 1 ならば、すべての駒を白にすることができました。関数 print_moves() で手順を表示します。手順は 1 手前の盤面の位置を使って queue をたどることで表示することができます。
そうでなければ、jump_table から動かす直線と駒の位置を求め、変数 l と p にセットします。そして、move_piece() で駒を動かして新しい盤面 newb を生成します。同一局面がなければ、queue に (newb, rc, p) を追加し、check[newb] に True をセットして探索を続けます。
●実行結果
さっそく実行してみたところ、最短手順は次のようになりました。
>>> s = time.time(); solver_bfs(); print(time.time() - s) [ S B B B B B B B B B B B ] [ B B W B B W B S B B B B ] [ B B S B B B B W B B B B ] [ B B B W S B B W B B B B ] [ B B B W B B W W B W B S ] [ B B B W B B S W B B B W ] [ S B B B B B B W B B B W ] [ W B W B B W B S B B B W ] [ W B S B B B B W B B B W ] [ W B B W S B B W B B B W ] [ W B B W W B W W B W B S ] [ W S B W W W W W W W B B ] [ W W W S W W W W W W B B ] [ W W W B W W B W W W S B ] [ S W W W W W W W W W W B ] [ W W B W W S W W W W W B ] [ W W B W W B W W B W W S ] [ W S B W W W W W W W W W ] [ W W W S W W W W W W W W ] 0.06575608253479004 実行環境 : Python3 (ver 3.8.10), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
-(0)-----
S
B B B B
B B
B B B B
B
-(1)----- -(2)----- -(3)----- -(4)----- -(5)----- -(6)-----
B B B B B S
B W B B B S B B B B W S B B W B B B W B B B B B
W B B B B B B W B S B B
S B B B W B B B W B B B W B W B W B B B W B B B
B B B S W W
-(7)----- -(8)----- -(9)----- -(10)---- -(11)---- -(12)----
W W W W W W
B W B B B S B B B B W S B B W W S B W W W W S W
W B B B B B B W W W W W
S B B B W B B B W B B B W B W B W W W B W W W B
W W W S B B
-(13)---- -(14)---- -(15)---- -(16)---- -(17)---- -(18)----
W S W W W W
W W B W W W W W W B W W W B W W S B W W W W S W
W B W W S W B W W W W W
W W W S W W W W W W W W W B W W W W W W W W W W
B B B S W W
図 : フリップ・イット・スターの解答
最短手数は 18 手、実行時間は約 0.06 秒でした。もちろん、単純な反復深化でも解くことができますが、ちょっと時間がかかります。詳細は プログラムリスト の関数 dfs() と solver_ids() をお読みください。ご参考までに実行結果を示します。
>>> s = time.time(); solver_ids(); print(time.time() - s) ----- 1 ----- ----- 2 ----- ----- 3 ----- ----- 4 ----- ----- 5 ----- ----- 6 ----- ----- 7 ----- ----- 8 ----- ----- 9 ----- ----- 10 ----- ----- 11 ----- ----- 12 ----- ----- 13 ----- ----- 14 ----- ----- 15 ----- ----- 16 ----- ----- 17 ----- ----- 18 ----- [ S B B B B B B B B B B B ] [ B B W B B W B S B B B B ] [ B B S B B B B W B B B B ] [ B B B W S B B W B B B B ] [ B B B W B B W W B W B S ] [ B B B W B B S W B B B W ] [ S B B B B B B W B B B W ] [ W B W B B W B S B B B W ] [ W B S B B B B W B B B W ] [ W B B W S B B W B B B W ] [ W B B W W B W W B W B S ] [ W S B W W W W W W W B B ] [ W W W S W W W W W W B B ] [ W W W B W W B W W W S B ] [ S W W W W W W W W W W B ] [ W W B W W S W W W W W B ] [ W W B W W B W W B W W S ] [ W S B W W W W W W W W W ] [ W W W S W W W W W W W W ] 11.508182764053345
実行時間は約 12 秒かかりました。やっぱり、単純な反復深化は遅いですね。興味のある方はプログラムの高速化に挑戦してみてください。
●最長手数の局面
最後に最長手数となる局面を幅優先探索で求めてみましょう。プログラムは次のようになります。
リスト : 最長手数の局面を求める
def solver_max():
xs = []
check = {}
for i in range(SIZE):
b = [W] * SIZE
b[i] = S
a = tuple(b)
xs.append((a, i))
check[a] = True
move = 0
while True:
ys = []
for b, s in xs:
for l, p in jump_table[s]:
newb = move_piece(b, l, s, p)
if newb in check: continue
ys.append((newb, p))
check[newb] = True
if not ys: break
xs = ys
move += 1
print('最長手数 =', move, "個数 =", len(xs))
for b, _ in xs: print_board(b)
print('状態の総数 =', len(check))
リスト xs は move 手で生成した盤面を格納します。リスト check は同一局面のチェックに使用します。ゴールの局面は SIZE 通りあるので、for ループで SIZE 通りの盤面を生成して xs と check に追加します。あとは while ループで move + 1 手の盤面を生成します。
リスト ys に move + 1 手の盤面を格納します。for ループで xs から盤面を一つずつ取り出し、move_piece() で新しい盤面 newb を生成します。同一局面がなければ、ys と check に newb を追加します。for ループを終了したら、ys にデータがあるかチェックします。ys が空リストならば xs が最長手数の盤面になります。break で while ループを脱出します。そうでなければ、xs を ys にセットし、move を +1 して探索を続けます。
●実行結果
さっそく実行してみたところ、最長手数の局面は次のようになりました。
>>> s = time.time(); solver_max(); print(time.time() - s) 最長手数 = 21 個数 = 24 [ B B W B B B S B W B B B ] [ B B B S B W B B B W B B ] [ B B B W B S B B B W B B ] [ B B S B B B W B W B B B ] [ B B W B B B W B S B B B ] [ B B W W B B B B B B B S ] [ B B B W S W W B W B B B ] [ B B B W B W B B S W B B ] [ B S B B B B W B B W B B ] [ B B B B S W B B W B B B ] [ B B W W B B B B W W B S ] [ B B W B B W B B B B S B ] [ B B B W B W W S W B B B ] [ B B B W B W S B B W B B ] [ S B B B B B B B W W B B ] [ B B B W B B W S B B B B ] [ B B W B B W W B B W S B ] [ B S W B B W W B B W B B ] [ B B W B B B W B W S B B ] [ B B W B B S W B W B B B ] [ B B B W B W B B B S B B ] [ B B W S B B W B W B B B ] [ S B W W B B B B W W B B ] [ B B S W B W B B B W B B ] 状態の総数 = 24576 0.12460827827453613
B S B B B B
B S W B B W W B B W S B B B W B B W B B B W B B
W B B B B W W B S W B W
B B W B B W W B B W B B B B S B B W B B B W S B
B B B B B B
B B B S B B
S W B B B W B B B B W B B B B B B B W B B B W B
W W W W B W B B W S W W
B B W B B B W S S B B B B W W B B B W B S W B B
B B B B B B
B B B B B B
B W B B B W W B B B B S S B B B B B W B B B W S
W B B B W B B W W B W W
B B B S B W W B B W B B B B W B B S W B B W B B
B S B B B B
B B B B B B
B W W B B W B B B S B B B B W B B B S B B W B B
B B B W B W S B W B B S
B B B B B S B B B W B B B B W B B B W B B W B B
S B B B B B
図 : 最長手数 (21手) の局面
最長手数は 21 手、その局面は全部で 24 通りになりました。実行時間は約 0.13 秒、Python でも高速に求めることができました。生成した状態の総数は 24576 だったので、このパズルは駒をランダムに配置しても解くことができます。
●プログラムリスト
#
# flipstar.py : フリップ・イット・スター
#
# Copyright (C) 2022 Makoto Hiroi
#
# 盤面
# 0
# 1 2 3 4
# 5 6
# 7 8 9 10
# 11
# 盤面の大きさ
SIZE = 12
# 駒
S = 0
B = 1
W = 2
# 直線
line = [
[0, 2, 5, 7], [0, 3, 6, 10], [7, 8, 9, 10],
[1, 2, 3, 4], [1, 5, 8, 11], [4, 6, 9, 11]
]
# 駒の跳び先表 (直線の番号, 駒の位置)
jump_table = [
[(0, 5), (0, 7), (1, 6), (1, 10)], # 0
[(3, 3), (3, 4), (4, 8), (4, 11)], # 1
[(0, 7), (3, 4)], # 2
[(1, 10), (3, 1)], # 3
[(3, 1), (3, 2), (5, 9), (5, 11)], # 4
[(0, 0), (4, 11)], # 5
[(1, 0), (5, 11)], # 6
[(0, 0), (0, 2), (2, 9), (2, 10)], # 7
[(2, 10), (4, 1)], # 8
[(2, 7), (5, 4)], # 9
[(1, 0), (1, 3), (2, 7), (2, 8)], # 10
[(4, 1), (4, 5), (5, 4), (5, 6)], # 11
]
# 駒の移動
def move_piece(b, l, p1, p2):
xs = list(b)
# 駒と空き場所の交換
xs[p1], xs[p2] = xs[p2], xs[p1]
# 順番のチェック
if p2 < p1: p1, p2 = p2, p1
# 駒の裏返し
for i in range(4):
p3 = line[l][i]
if p1 < p3 < p2:
if xs[p3] == B:
xs[p3] = W
else:
xs[p3] = B
return tuple(xs)
# 盤面の表示
def print_board(b):
s = ['S', 'B', 'W']
print('[', end=' ')
for x in b:
print(s[x], end=' ')
print(']')
# 手順の表示
def print_moves(n, states):
if n > 0:
print_moves(states[n][1], states)
print_board(states[n][0])
# 幅優先探索 (start はタプル)
def bfs(start):
queue = [(start, -1, start.index(S))]
check = {}
check[start] = True
rc = 0
while rc < len(queue):
b, _, s = queue[rc]
if b.count(W) == SIZE - 1:
print_moves(rc, queue)
return
for l, p in jump_table[s]:
newb = move_piece(b, l, p, s)
if newb in check: continue
queue.append((newb, rc, p))
check[newb] = True
rc += 1
def solver_bfs():
start = [B] * SIZE
start[0] = S
bfs(tuple(start))
# 反復深化
def dfs(n, limit, space, moves):
b = moves[-1]
if n == limit:
if b.count(W) == SIZE - 1:
for a in moves[1:]: print_board(a)
return True
else:
for l, p in jump_table[space]:
newb = move_piece(b, l, p, space)
# newb -> b -> newb のチェック
if moves[-2] == newb: continue
moves.append(newb)
if dfs(n + 1, limit, p, moves): return True
moves.pop()
return False
def solver_ids():
start = [B] * SIZE
start[0] = S
dummy = [S] * SIZE
limit = 1
while True:
print(f'----- {limit} -----')
if dfs(0, limit, 0, [dummy, start]):
break
limit += 1
# 最長手数の局面
def solver_max():
xs = []
check = {}
for i in range(SIZE):
b = [W] * SIZE
b[i] = S
a = tuple(b)
xs.append((a, i))
check[a] = True
move = 0
while True:
ys = []
for b, s in xs:
for l, p in jump_table[s]:
newb = move_piece(b, l, s, p)
if newb in check: continue
ys.append((newb, p))
check[newb] = True
if not ys: break
xs = ys
move += 1
print('最長手数 =', move, "個数 =", len(xs))
for b, _ in xs: print_board(b)
print('状態の総数 =', len(check))
改訂 2022 年 11 月 5 日