M.Hiroi's Home Page

Puzzle DE Programming

フリップ・イット

[ Home | Puzzle ]

パズルの説明

「フリップ・イット (Flip It)」は芦ヶ原伸之氏が考案されたパズルで、すべての駒を裏返しにするのが目的です。今回はリバーシの駒を使うことにしましょう。次の図を見てください。

フリップ・イットのルールは簡単です。ある駒は他の駒を跳び越して空き場所へ移動することができます。空き場所の隣にある駒は、跳び越す駒がないので移動できません。このとき、跳び越された駒は裏返しにされますが、跳んだ駒はそのままです。図では 5 の位置にある駒が 0 へ跳び、それから 2 の駒が 5 へ跳んだ場合を示しています。このあと 0 -> 2, 5 -> 0 と跳ぶと、すべての駒を白にすることができます。

それでは問題です。

参考文献 12 の問題は 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 ]

(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 して探索を続けます。

●実行結果 (2)

実行結果は次のようになりました。

>>> 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))

Copyright (C) 2022 Makoto Hiroi
All rights reserved.

[ Home | Puzzle ]