「フリップ・イット (Flip It)」は芦ヶ原伸之氏が考案されたパズルで、すべての駒を裏返しにするのが目的です。今回はリバーシの駒を使うことにしましょう。次の図を見てください。
０ １ ２ ３ ４ ５ ０ １ ２ ３ ４ ５
┌─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┐
│ │●│●│●│●│●│ │●│○│○│○│○│ │
└─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┘
│ │
┌─────────┘ └─────┐
↓ ↓
┌─┬─┬─┬─┬─┬─┐ ┌─┬─┬─┬─┬─┬─┐
│●│○│○│○│○│ │ │●│○│ │●│●│○│
└─┴─┴─┴─┴─┴─┘ └─┴─┴─┴─┴─┴─┘
５の駒が０へ跳んだ場合 ２の駒が５へ跳んだ場合
図 : フリップ・イットのルール
フリップ・イットのルールは簡単です。ある駒は他の駒を跳び越して空き場所へ移動することができます。空き場所の隣にある駒は、跳び越す駒がないので移動できません。このとき、跳び越された駒は裏返しにされますが、跳んだ駒はそのままです。図では 5 の位置にある駒が 0 へ跳び、それから 2 の駒が 5 へ跳んだ場合を示しています。このあと 0 -> 2, 5 -> 0 と跳ぶと、すべての駒を白にすることができます。
それでは問題です。
┌─┬─┬─┬─┬─┬─┐
(A) │●│●│ │●│●│●│
└─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┐
(B) │●│ │○│●│●│●│●│
└─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┬─┐
(C) │●│ │○│○│○│●│●│●│
└─┴─┴─┴─┴─┴─┴─┴─┘
問題 : フリップ・イット
参考文献『ブルーバックス B-1377 超々難問数理パズル 解けるものなら解いてごらん』の問題は 4 つの駒を使っているので、本ページでは駒の個数を増やしてみました。すべての駒を白にする最短手順を求めてください。
それではプログラムを作りましょう。使用するプログラミング言語は Python3 (ver 3.8.10) です。アルゴリズムは単純な幅優先探索を使います。最初に、駒の置き方が何通りあるか数えます。これは空き場所の配置から考えた方が簡単です。
盤面の大きさを N とすると、空き場所の配置は N 通りあります。残りは黒か白のどちらかなので、駒の配置は 2 N - 1 通りあります。したがって、全体では N * 2 N - 1 通りになります。実際に計算してみると、N = 6 で 192 通り、N = 7 で 448 通り、N = 8 で 1024 通りになります。大きな数ではないので、同一局面のチェックは線形探索でいいでしょう。
次に、駒を動かして新しい盤面を生成する関数 move_piece() を作ります。次のリストを見てください。
リスト : 駒の移動
# 定数
S = 0
B = 1
W = 2
# 駒の反転
def rev_piece(b, s, e):
for i in range(s, e):
if b[i] == B:
b[i] = W
else:
b[i] = B
# 駒の移動
def move_piece(b, s, e):
newb = b[:]
if s < e:
rev_piece(newb, s + 1, e)
else:
rev_piece(newb, e + 1, s)
newb[s], newb[e] = newb[e], newb[s]
return newb
引数 b が盤面、s と e が移動する駒の位置と空き場所の位置です。move_piece() は b をコピーするとともに、s と e の間の駒を裏返しにして、s と e の位置にある駒と空き場所を入れ替えます。駒の裏返しは関数 rev_piece() で行います。引数 s が始点、e が終点を表します。s <= i < e の駒を反転します。
次は、幅優先探索で最短手順を探索する関数 bfs() を作ります。
リスト : 幅優先探索
def bfs(start):
queue = [[start]]
check = [start]
while len(queue) > 0:
move = queue.pop(0)
b = move[-1]
s = b.index(0)
if b.count(W) == len(b) - 1:
print_moves(move)
return
for i in range(len(b)):
if abs(i - s) <= 1: continue
newb = move_piece(b, i, s)
if newb in check: continue
xs = move[:]
xs.append(newb)
queue.append(xs)
check.append(newb)
引数 start がスタートの盤面です。リスト queue をキューとして使い、リスト check を同一局面のチェックに使います。while ループでキューにデータがある間は探索を続けます。次に、キューから手順を一つ取り出して変数 move にセットします。move の末尾要素が現在の盤面です。それを変数 b にセットし、メソッド index() で空き場所の位置を求めて変数 s にセットします。
b がすべて白 (W) ならば、白の個数は len(b) - 1 になります。関数 print_moves() で手順を表示して、return で探索を終了します。そうでなければ、for ループで 0 番目から len(b) - 1 番目までの駒を動かします。変数 i は動かす駒の位置を表します。空き場所の隣の駒は動かせないので、abs(i - s) が 1 以下であれば contiune でループの先頭に戻ります。
次に、move_piece() で i 番目の駒を動かして新しい盤面 newb を生成し、演算子 in で同一局面があるかチェックします。同一局面がなれければ、move をコピーして変数 xs にセットし、xs の末尾に newb を追加します。そして、queue に xs を、check に newb を追加して探索を続行します。
あとのプログラムは簡単なので説明は割愛させていただきます。詳細はプログラムリストをお読みください。
それでは実行結果を示します。
>>> bfs([B,B,S,B,B,B]) [ B B S B B B ] [ S W B B B B ] [ B B W S B B ] [ B B W B W S ] [ B B S W B W ] [ S W B W B W ] [ W B W S B W ] [ W S B B B W ] [ W W W W W S ] >>> bfs([B,S,W,B,B,B,B]) [ B S W B B B B ] [ B B B S B B B ] [ S W W B B B B ] [ W B S B B B B ] [ W B B W S B B ] [ W B B W B W S ] [ W B B S W B W ] [ W B B B B S W ] [ S W W W W W W ] >>> bfs([B,S,W,W,W,B,B,B]) [ B S W W W B B B ] [ B W B S W B B B ] [ S B W B W B B B ] [ W W S B W B B B ] [ W W W W S B B B ] [ W W W W B W W S ] [ S B B B W B B W ] [ W W W W S B B W ] [ W W W W W W W S ]
（Ａ） （Ｂ） （Ｃ）
0: ● ● ＿ ● ● ● ● ＿ ○ ● ● ● ● ● ＿ ○ ○ ○ ● ● ●
1: ＿ ○ ● ● ● ● ● ● ● ＿ ● ● ● ● ○ ● ＿ ○ ● ● ●
2: ● ● ○ ＿ ● ● ＿ ○ ○ ● ● ● ● ＿ ● ○ ● ○ ● ● ●
3: ● ● ○ ● ○ ＿ ○ ● ＿ ● ● ● ● ○ ○ ＿ ● ○ ● ● ●
4: ● ● ＿ ○ ● ○ ○ ● ● ○ ＿ ● ● ○ ○ ○ ○ ＿ ● ● ●
5: ＿ ○ ● ○ ● ○ ○ ● ● ○ ● ○ ＿ ○ ○ ○ ○ ● ○ ○ ＿
6: ○ ● ○ ＿ ● ○ ○ ● ● ＿ ○ ● ○ ＿ ● ● ● ○ ● ● ○
7: ○ ＿ ● ● ● ○ ○ ● ● ● ● ＿ ○ ○ ○ ○ ○ ＿ ● ● ○
8: ○ ○ ○ ○ ○ ＿ ＿ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ○ ＿
図 : フリップ・イットの解答
(A), (B), (C) ともに最短手数は 8 手になりました。実は、これが最長手数の局面となります。ちなみに、駒の個数が 4 つの場合だと、最長手数は 10 手と長くなります。また、最後の白石の位置を限定すると、手数が長くなる場合もあります。たとえば、(A) の問題でゴールを "＿ ○ ○ ○ ○ ○" とすると、最短手数は 9 手になります。
なお、反復深化でも簡単にプログラムすることができます。興味のある方はプログラムリストの関数 dfs() と ids() をお読みください。
次は、最長手数の局面を幅優先探索で求めてみましょう。
リスト : 最長手数の探索
def solver_max(n):
xs = []
check = []
for i in range(n):
b = [W] * n
b[i] = S
xs.append(b)
check.append(b)
move = 0
while True:
ys = []
for b in xs:
s = b.index(0)
for i in range(0, len(b)):
if abs(i - s) <= 1: continue
newb = move_piece(b, i, s)
if newb not in check:
ys.append(newb)
check.append(newb)
if not ys: break
move += 1
xs = ys
print('最長手数 =', move, '総数 =', len(xs))
for b in xs[:8]: print(b)
print('状態の総数 =', len(check))
関数 solve_max() の引数 n は盤面のサイズを表します。リスト xs は move 手で生成した盤面を格納します。リスト check は同一局面のチェックに使用します。ゴールの局面は n 通りあるので、for ループで n 通りの盤面を生成して 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 して探索を続けます。
実行結果は次のようになりました。
>>> solver_max(5) 最長手数 = 10 総数 = 3 [ B S W B B ] [ B B S B B ] [ B B W S B ] 状態の総数 = 80 >>> solver_max(6) 最長手数 = 8 総数 = 4 [ B B B S B B ] [ B B B W S B ] [ B B S B B B ] [ B S W B B B ] 状態の総数 = 192 >>> solver_max(7) 最長手数 = 8 総数 = 4 [ B S W B B B B ] [ B B S B B B B ] [ B B B B S B B ] [ B B B B W S B ] 状態の総数 = 448 >>> solver_max(8) 最長手数 = 8 総数 = 6 [ B B B W W W S B ] [ B B B B B S B B ] [ B B B B B W S B ] [ B S W W W B B B ] [ B S W B B B B B ] [ B B S B B B B B ] 状態の総数 = 1024
フリップ・イットの場合、盤面を大きくしたからといって、最長手数が長くなるとは限らないようです。興味のある方は、より大きな盤面で試してみてください。
ところで、フリップ・イットのルールでは空き場所の隣の駒を動かすことはできません。ルールを「空き場所の隣の駒を動かしてもよい」ことに変更して最長手数の局面を求めてみたところ、結果は次のようになりました。
>>> solver_max1(5) 最長手数 = 6 総数 = 1 [ B B S B B ] 状態の総数 = 80 >>> solver_max1(6) 最長手数 = 6 総数 = 6 [ B B S W B B ] [ B B B W S B ] [ B B B S B B ] [ B S W B B B ] [ B B W S B B ] [ B B S B B B ] 状態の総数 = 192 >>> solver_max1(7) 最長手数 = 7 総数 = 3 [ B B S W B B B ] [ B B B W S B B ] [ B B B S B B B ] 状態の総数 = 448 >>> solver_max1(8) 最長手数 = 7 総数 = 20 [ B B S W B W B B ] [ B B S W W B B B ] [ B B B W B W S B ] [ B B B W S W B B ] [ B B B W B S B B ] [ B B B S B W B B ] [ B B B S W B B B ] [ B B B B W W S B ] 状態の総数 = 1024
どうやら、このルールの方が簡単に解くことができるようです。
#
# flipit.py : フリップ・イット
#
# Copyright (C) 2022 Makoto Hiroi
#
# 定数
S = 0
B = 1
W = 2
# 駒の反転
def rev_piece(b, s, e):
for i in range(s, e):
if b[i] == B:
b[i] = W
else:
b[i] = B
# 駒の移動
def move_piece(b, s, e):
newb = b[:]
if s < e:
rev_piece(newb, s + 1, e)
else:
rev_piece(newb, e + 1, s)
newb[s], newb[e] = newb[e], newb[s]
return newb
# 盤面の表示
def print_board(b):
s = ('S', 'B', 'W')
print('[', end=' ')
for n in b:
print(s[n], end= ' ')
print(']')
# 手順の表示
def print_moves(moves):
for b in moves: print_board(b)
print()
# 幅優先探索
def bfs(start):
queue = [[start]]
check = [start]
while len(queue) > 0:
move = queue.pop(0)
b = move[-1]
s = b.index(0)
if b.count(W) == len(b) - 1:
print_moves(move)
return
for i in range(len(b)):
if abs(i - s) <= 1: continue
newb = move_piece(b, i, s)
if newb in check: continue
xs = move[:]
xs.append(newb)
queue.append(xs)
check.append(newb)
# 反復深化
def dfs(n, limit, moves):
global cnt
b = moves[-1]
if n == limit:
if b.count(W) == len(b) - 1:
print_moves(moves)
cnt += 1
else:
s = b.index(S)
for i in range(len(b)):
if abs(i - s) <= 1: continue
newb = move_piece(b, i, s)
if newb in moves: continue
moves.append(newb)
dfs(n + 1, limit, moves)
moves.pop()
def ids(start):
global cnt
cnt = 0
i = 1
while cnt == 0:
print(f'----- {i} -----')
dfs(0, i, [start])
i += 1
print(cnt)
# 最長手数の局面
def solver_max(n):
xs = []
check = []
for i in range(n):
b = [W] * n
b[i] = S
xs.append(b)
check.append(b)
move = 0
while True:
ys = []
for b in xs:
s = b.index(0)
for i in range(0, len(b)):
if abs(i - s) <= 1: continue
newb = move_piece(b, i, s)
if newb not in check:
ys.append(newb)
check.append(newb)
if not ys: break
move += 1
xs = ys
print('最長手数 =', move, '総数 =', len(xs))
for b in xs[:8]: print_board(b)
print('状態の総数 =', len(check))
# ルール変更
def solver_max1(n):
xs = []
check = []
for i in range(n):
b = [W] * n
b[i] = S
xs.append(b)
check.append(b)
move = 0
while True:
ys = []
for b in xs:
s = b.index(0)
for i in range(0, len(b)):
if i == s: continue
newb = move_piece(b, i, s)
if newb not in check:
ys.append(newb)
check.append(newb)
if not ys: break
move += 1
xs = ys
print('最長手数 =', move, '総数 =', len(xs))
for b in xs[:8]: print_board(b)
print('状態の総数 =', len(check))