Puzzle DE Programming / フリップ・イット・スクエア

問題の説明

「フリップ・イット (Flip It)」は芦ヶ原伸之氏 (参考文献 12) が考案されたパズルで、すべての駒を裏返しにするのが目的です。フリップ・イット・スターでは、駒の配置を六芒星の形にしたパズルを解きました。今回は駒を正方形に配置した「フリップ・イット・スクエア」を解いてみましょう。それでは問題です。

ルールは「フリップ・イット」と同じで、駒はほかの駒を跳び越すことで移動することができます。詳しい説明はフリップ・イットをお読みくださいませ。今回は駒の移動方向を縦と横の 2 方向に限定し、斜め跳びは禁止することにします。すべての駒を白にする最短手順を求めてください。

興味のある方は、斜め跳びを許可した場合の最短手順にも挑戦してみてください。

●幅優先探索による解法

まずは単純な幅優先探索でプログラムを作りましょう。使用するプログラミング言語は Python3 (PyPy3 7.3.1) です。最初に駒の置き方が何通りあるか数えましょう。これは空き場所の配置から考えた方が簡単です。盤面の大きさは 16 なので、空き場所の配置は 16 通りあります。残りは黒か白のどちらかなので、駒の配置は 2 ¹⁵ = 327688 通りあります。したがって、全体では 16 * 32768 = 524288 通りになります。けっこう大きな数になりますね。そこで、同一局面のチェックには Python の辞書を使うことにします。

次は大域変数を定義します。

リスト : 大域変数の定義

# 盤面の大きさ
SIZE = 16

# 駒
S = 0
B = 1
W = 2

# 直線
line = [
    [0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15],
    [0, 4, 8, 12], [1, 5, 9, 13], [2, 6, 10, 14], [3, 7, 11, 15]
]

# 駒の跳び先表 (直線の番号, 駒の位置)
jump_table = [
    [(0, 2), (0, 3), (4, 8), (4, 12)],   # 0
    [(0, 3), (5, 9), (5, 13)],           # 1
    [(0, 0), (6, 10), (6, 14)],          # 2
    [(0, 0), (0, 1), (7, 11), (7, 15)],  # 3
    [(1, 6), (1, 7), (4, 12)],           # 4
    [(1, 7), (5, 13)],                   # 5
    [(1, 4), (6, 14)],                   # 6
    [(1, 4), (1, 5), (7, 15)],           # 7
    [(2, 10), (2, 11), (4, 0)],          # 8
    [(2, 11), (5, 1)],                   # 9
    [(2, 8), (6, 2)],                    # 10
    [(2, 8), (2, 9), (7, 3)],            # 11
    [(3, 14), (3, 15), (4, 0), (4, 4)],  # 12
    [(3, 15), (5, 1), (5, 5)],           # 13
    [(3, 12), (6, 2), (6, 6)],           # 14
    [(3, 12), (3, 13), (7, 3), (7, 7)]   # 15
]

盤面は一次元配列 (Python のタプル) で表します。盤面の位置と配列の添字の対応は、上図のように定義します。すると、8 本の直線はリスト line で表すことができます。駒の移動は跳び先表を定義すると簡単です。jump_table は空き場所を基準にして、タプル (直線の番号, 移動する駒の位置) を格納しています。

あとはフリップ・イット・スターで作成したプログラムととほとんど同じです。詳細はプログラムリスト１をお読みください。

●実行結果 (1)

さっそく実行してみたところ、最短手順は次のようになりました。

>>>> s = time.time(); solver_bfs(5); print(time.time() - s)
[ B B B B B S B B B B B B B B B B ]
[ B B B B B B W S B B B B B B B B ]
[ B B B B B B W B B B B W B B B S ]
[ B B B B B B W B B B B W S W W B ]
[ B B B B B B W B B B B W W B S B ]
[ B B S B B B B B B B W W W B B B ]
[ S W B B B B B B B B W W W B B B ]
[ B B W S B B B B B B W W W B B B ]
[ B B W W B B B W B B W S W B B B ]
[ B B W W B B B W S W B B W B B B ]
[ S B W W W B B W B W B B W B B B ]
[ W B W W B B B W W W B B S B B B ]
[ W B W W B B B W W W B B B W W S ]
[ W B W W B B B S W W B W B W W W ]
[ W B W W S W W B W W B W B W W W ]
[ W B W W B W W B B W B W S W W W ]
[ S B W W W W W B W W B W W W W W ]
[ W W B S W W W B W W B W W W W W ]
[ W W B W W W W W W W B S W W W W ]
[ W W B W W W W W S B W W W W W W ]
[ W W B W W W W W W W S W W W W W ]
[ W W S W W W B W W W B W W W W W ]
[ W W W W W W W W W W W W W W S W ]
1.5339834690093994

実行環境 : PyPy3 (ver 7.3.1), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz

  - 0 ---
  B B B B
  B S B B
  B B B B
  B B B B

  - 1 ---   - 2 ---   - 3 ---   - 4 ---   - 5 ---   - 6 ---  
  B B B B   B B B B   B B B B   B B B B   B B S B   S W B B  
  B B W S   B B W B   B B W B   B B W B   B B B B   B B B B  
  B B B B   B B B W   B B B W   B B B W   B B W W   B B W W  
  B B B B   B B B S   S W W B   W B S B   W B B B   W B B B  

  - 7 ---   - 8 ---   - 9 ---   - 10 --   - 11 --   - 12 --  
  B B W S   B B W W   B B W W   S B W W   W B W W   W B W W  
  B B B B   B B B W   B B B W   W B B W   B B B W   B B B W  
  B B W W   B B W S   S W B B   B W B B   W W B B   W W B B  
  W B B B   W B B B   W B B B   W B B B   S B B B   B W W S  

  - 13 --   - 14 --   - 15 --   - 16 --   - 17 --   - 18 --  
  W B W W   W B W W   W B W W   S B W W   W W B S   W W B W  
  B B B S   S W W B   B W W B   W W W B   W W W B   W W W W  
  W W B W   W W B W   B W B W   W W B W   W W B W   W W B S  
  B W W W   B W W W   S W W W   W W W W   W W W W   W W W W  

  - 19 --   - 20 --   - 21 --   - 22 --  
  W W B W   W W B W   W W S W   W W W W  
  W W W W   W W W W   W W B W   W W W W  
  S B W W   W W S W   W W B W   W W W W  
  W W W W   W W W W   W W W W   W W S W  


            図 : フリップ・イット・スクエアの解答

最短手数は 22 手になりました。実は、これが斜め跳びを禁止した場合の最長手数になります。実行時間は約 1.6 秒でした。

●反復深化による解法

もちろん、反復深化でも簡単にプログラムを作ることができます。次のリストを見てください。

リスト : 反復深化

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(n):
    start = [B] * SIZE
    start[n] = S
    dummy = [S] * SIZE
    limit = 1
    while True:
        print(f'----- {limit} -----')
        if dfs(0, limit, n, [dummy, start]):
            break
        limit += 1

関数 dfs() の引数 n が手数、limit が手数の上限値、moves が移動手順を表すリストです。moves の要素は盤面です。手数が上限値に達したら、パズルが解けたかチェックします。駒がすべて白になったら手順 moves を表示します。上限値に達していない場合は、駒を移動して新しい局面を作ります。

フリップ・イットのように、元の局面に戻すことが可能 (可逆) なパズルの場合、単純な深さ優先探索では同じ移動手順を何度も繰り返すことがあります。そうなると、とんでもない解を出力するだけではなく、再帰呼び出しが深くなるとスタックがオーバーフローしてプログラムの実行が停止してしまいます。

このような場合、局面の履歴を保存しておいて同じ局面がないかチェックすることで、解を求めることができるようになります。ただし、同一局面をチェックする分だけ時間が余分にかかりますし、最初に見つかる解が最短手数とは限りません。

反復深化では深さが制限されているため、同一局面のチェックを行わなくてもスタックオーバーフローが発生することはありません。そのかわり、無駄な探索はどうしても避けることができません。フリップ・イットの場合、1 手前に動かした駒を再度動かすと 2 手前の局面に戻ってしまいます。完全ではありませんが、このチェックを入れるだけでもかなりの無駄を省くことができます。

プログラムでは、moves に盤面を格納しているので、新しい盤面 newb が 2 手前の局面 move[-2] と同じにならないことをチェックしています。なお、moves[0] はダミーデータ (要素がすべて S のリスト) になります。moves[1] 以降のデータが実際に生成した盤面になります。

●実行結果 (2)

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

>>>> s = time.time(); solver_ids(5); print(time.time() - s)
----- 1 -----
----- 2 -----
----- 3 -----
----- 4 -----
----- 5 -----
----- 6 -----
----- 7 -----
----- 8 -----
----- 9 -----
----- 10 -----
----- 11 -----
----- 12 -----
----- 13 -----
----- 14 -----
----- 15 -----
----- 16 -----
----- 17 -----
----- 18 -----
----- 19 -----
----- 20 -----
----- 21 -----
----- 22 -----
[ B B B B B S B B B B B B B B B B ]
[ B B B B B B W S B B B B B B B B ]
[ B B B B B B W B B B B W B B B S ]
[ B B B B B B W B B B B W S W W B ]
[ B B B B B B W B B B B W W B S B ]
[ B B S B B B B B B B W W W B B B ]
[ S W B B B B B B B B W W W B B B ]
[ B B W S B B B B B B W W W B B B ]
[ B B W W B B B W B B W S W B B B ]
[ B B W W B B B W S W B B W B B B ]
[ S B W W W B B W B W B B W B B B ]
[ W B W W B B B W W W B B S B B B ]
[ W B W W B B B W W W B B B W W S ]
[ W B W W B B B S W W B W B W W W ]
[ W B W W S W W B W W B W B W W W ]
[ W B W W B W W B B W B W S W W W ]
[ S B W W W W W B W W B W W W W W ]
[ W W B S W W W B W W B W W W W W ]
[ W W B W W W W W W W B S W W W W ]
[ W W B W W W W W S B W W W W W W ]
[ W W B W W W W W W W S W W W W W ]
[ W W S W W W B W W W B W W W W W ]
[ W W W W W W W W W W W W W W S W ]
47.88655209541321

実行時間は約 48 秒かかりました。単純な反復深化なので、時間がかかるのはしかたがないですね。そこで、次は下限値枝刈り法を使ってプログラムの高速化に挑戦してみましょう。

●下限値枝刈り法による高速化

フリップ・イット・スクエアの場合、簡単な方法で下限値を求めることができます。4 つのコーナーに注目してください。コーナーにある駒はほかの駒から跳び越されることはありません。したがって、コーナーの駒が黒の場合、まずコーナーから別の場所に移動して、それから他の駒に跳び越されないと白にすることはできません。よって、コーナーにある黒駒を裏返しにするには、最低でも 2 手必要になることがわかります。これを下限値として利用することにしましょう。

プログラムは次のようになります。

リスト : 下限値枝刈り法による解法

# 下限値を求める
def get_lower_value(b):
    lower = 0
    for i in [0, 3, 12, 15]:
        if b[i] == B: lower += 2
    return lower

# 反復深化＋下限値枝刈り法
def dfs1(n, limit, space, moves):
    b = moves[-1]
    if n + get_lower_value(b) > limit: return False
    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 dfs1(n + 1, limit, p, moves): return True
            moves.pop()
    return False

def solver_ids1(n):
    start = [B] * SIZE
    start[n] = S
    dummy = [S] * SIZE
    limit = get_lower_value(start)
    while True:
        print(f'----- {limit} -----')
        if dfs1(0, limit, n, [dummy, start]):
            break
        limit += 1

関数 get_lower_value() は盤面 b の下限値を求めます。下限値の計算はコーナーにある黒駒を数えて 2 倍するだけです。あとは、関数 dfs1() で get_lower_value() を呼び出して、「手数＋下限値」が上限値 limit を超えていれば枝刈りを行います。関数 solver_ids1() では limit を get_lower_value(start) の値で始めます。プログラムの修正はこれだけです。とても簡単ですね。

さっそく実行してみたところ、実行時間は約 4.6 秒まで短縮できました。簡単な方法で下限値を求めましたが、その効果は絶大ですね。M.Hiroi もちょっと驚きました。

●最長手数の局面

次は最長手数の局面を求めてみましょう。プログラムは次のようになります。

リスト : 最長手数の局面

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

フリップ・イット・スターで作成したプログラムとほとんど同じなので、詳しい説明は不要だと思います。

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

>>>> s = time.time(); solver_max(); print(time.time() - s)
最長手数 = 22 個数 = 4
[ B B B B B S B B B B B B B B B B ]
[ B B B B B B B B B B S B B B B B ]
[ B B B B B B S B B B B B B B B B ]
[ B B B B B B B B B S B B B B B B ]
状態の総数 = 524288
2.357588052749634

  B B B B   B B B B   B B B B   B B B B
  B S B B   B B B B   B B S B   B B B B
  B B B B   B B S B   B B B B   B S B B
  B B B B   B B B B   B B B B   B B B B


        図 : 最長手数の局面

最長手数は 22 手で、4 通りの解が出力されました。重複解を除くと、最長手数の局面は 1 通りしかありません。また、生成した状態の総数は 524288 通りなので、このパズルは駒をランダムに配置しても解けることがわかります。実行時間は約 2.4 秒でした。

●規則の変更

次は、斜め跳びを許可した場合の最短手順を求めてみましょう。プログラムは直線の定義 (line) と駒の跳び先表 (move_pattern_table) を変更するだけです。次のリストを見てください。

リスト : 直線と跳び先表の変更

# 直線
line = [
    [0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15],
    [0, 4, 8, 12], [1, 5, 9, 13], [2, 6, 10, 14], [3, 7, 11, 15],
    [0, 5, 10, 15], [1, 6, 11, 99], [4, 9, 14, 99],  # 追加
    [3, 6, 9, 12], [2, 5, 8, 99], [7, 10, 13, 99]    # 追加
]

# 駒の跳び先表 (直線の番号, 駒の位置)
jump_table = [
    [(0, 2), (0, 3), (4, 8), (4, 12), (8, 10), (8, 15)],   # 0
    [(0, 3), (5, 9), (5, 13), (9, 11)],           # 1
    [(0, 0), (6, 10), (6, 14), (12, 8)],          # 2
    [(0, 0), (0, 1), (7, 11), (7, 15), (11, 9), (11, 12)], # 3
    [(1, 6), (1, 7), (4, 12), (10, 14)],          # 4
    [(1, 7), (5, 13), (8, 15)],                   # 5
    [(1, 4), (6, 14), (11, 12)],                  # 6
    [(1, 4), (1, 5), (7, 15), (13, 13)],          # 7
    [(2, 10), (2, 11), (4, 0), (12, 2)],          # 8
    [(2, 11), (5, 1), (11, 3)],                   # 9
    [(2, 8), (6, 2), (8, 0)],                     # 10
    [(2, 8), (2, 9), (7, 3), (9, 1)],             # 11
    [(3, 14), (3, 15), (4, 0), (4, 4), (11, 3), (11, 6)], # 12
    [(3, 15), (5, 1), (5, 5), (13, 7)],           # 13
    [(3, 12), (6, 2), (6, 6), (10, 4)],           # 14
    [(3, 12), (3, 13), (7, 3), (7, 7), (8, 0), (8, 5)]    # 15
]

配列 line に斜めの直線を 6 本追加します。99 はダミーデータです。そして、追加した直線に対する駒の移動先を jump_table に追加します。たとえば、空き場所が 0 の場合、直線 8 の移動先の位置 (10 と 15) を追加します。このように、斜め跳びを許すと移動できる駒の個数が増えるので、探索する局面数は大幅に増加することになります。単純な反復深化ではめちゃくちゃ時間がかかるでしょう。ご注意くださいませ。

プログラムリスト２

●実行結果

さっそく実行してみたところ、最短手順は次のようになりました。図では黒石を 1, 白石を 2, 空き場所を 0 で表しています。

>>>> s = time.time(); solver_bfs(5); print(time.time() - s)
[ B B B B B S B B B B B B B B B B ]
[ B B B B B B W S B B B B B B B B ]
[ B B B B B B W B B B B W B B B S ]
[ B B B B B B W B B B B W S W W B ]
[ B B B B B B W B B B B W W B S B ]
[ B B S B B B B B B B W W W B B B ]
[ B B B B B W B B S B W W W B B B ]
[ S B B B W W B B B B W W W B B B ]
[ B W W S W W B B B B W W W B B B ]
[ B W W W W W B W B B W S W B B B ]
[ B W W W W W B W S W B B W B B B ]
[ S W W W B W B W B W B B W B B B ]
[ W W W W W W B W W W B B S B B B ]
[ W W W W W W B W W W B B B W W S ]
[ W W W W W W B S W W B W B W W W ]
[ W W W W S B W W W W B W B W W W ]
[ W W W W B B W W B W B W S W W W ]
[ S W W W W B W W W W B W W W W W ]
[ W W W W W W W W W W W W W W W S ]
3.6628482341766357

>>>> s = time.time(); solver_ids1(5); print(time.time() - s)
----- 8 -----
----- 9 -----
----- 10 -----
----- 11 -----
----- 12 -----
----- 13 -----
----- 14 -----
----- 15 -----
----- 16 -----
----- 17 -----
----- 18 -----
[ B B B B B S B B B B B B B B B B ]
[ B B B B B B W S B B B B B B B B ]
[ B B B B B B W B B B B W B B B S ]
[ B B B B B B W B B B B W S W W B ]
[ B B B B B B W B B B B W W B S B ]
[ B B S B B B B B B B W W W B B B ]
[ B B B B B W B B S B W W W B B B ]
[ S B B B W W B B B B W W W B B B ]
[ B W W S W W B B B B W W W B B B ]
[ B W W W W W B W B B W S W B B B ]
[ B W W W W W B W S W B B W B B B ]
[ S W W W B W B W B W B B W B B B ]
[ W W W W W W B W W W B B S B B B ]
[ W W W W W W B W W W B B B W W S ]
[ W W W W W W B S W W B W B W W W ]
[ W W W W S B W W W W B W B W W W ]
[ W W W W B B W W B W B W S W W W ]
[ S W W W W B W W W W B W W W W W ]
[ W W W W W W W W W W W W W W W S ]
21.177791357040405

  - 0 ---
  B B B B
  B S B B
  B B B B
  B B B B

  - 1 ---   - 2 ---   - 3 ---   - 4 ---   - 5 ---   - 6 ---  
  B B B B   B B B B   B B B B   B B B B   B B S B   B B B B  
  B B W S   B B W B   B B W B   B B W B   B B B B   B W B B  
  B B B B   B B B W   B B B W   B B B W   B B W W   S B W W  
  B B B B   B B B S   S W W B   W B S B   W B B B   W B B B  

  - 7 ---   - 8 ---   - 9 ---   - 10 --   - 11 --   - 12 --  
  S B B B   B W W S   B W W W   B W W W   S W W W   W W W W  
  W W B B   W W B B   W W B W   W W B W   B W B W   W W B W  
  B B W W   B B W W   B B W S   S W B B   B W B B   W W B B  
  W B B B   W B B B   W B B B   W B B B   W B B B   S B B B  

  - 13 --   - 14 --   - 15 --   - 16 --   - 17 --   - 18 --  
  W W W W   W W W W   W W W W   W W W W   S W W W   W W W W  
  W W B W   W W B S   S B W W   B B W W   W B W W   W W W W  
  W W B B   W W B W   W W B W   B W B W   W W B W   W W W W  
  B W W S   B W W W   B W W W   S W W W   W W W W   W W W S  


          図 : フリップ・イット・スクエアの解答

最短手数は 18 手、斜め跳びを許した方が短い手数で解けるようです。実は、これが斜め跳びを許可した場合の最長手数になります。実行時間は幅優先探索で約 3.7 秒、反復深化＋下限値枝刈り法で約 21.2 秒かかりました。下限値の精度が低いので、下限値枝刈り法でも時間がかかりますね。

最後に、最長手数の局面を求めます。

>>>> s = time.time(); solver_max(); print(time.time() - s)
最長手数 = 18 個数 = 20
[ B B B B B B W B B S B B B B B B ]
[ B B B B B B S B B B B B B B B B ]
[ B B B B B S W B B W W B B B B B ]
[ B B B B B W B B B B S B B B B B ]
[ B B B B B S B B B W B B B B B B ]
[ B B B B B W S B B B B B B B B B ]
[ B B B B B B S B B W B B B B B B ]
[ B B B B B W B B B S B B B B B B ]
[ B B B B B B B B B S B B B B B B ]
[ B B B B B S W B B B B B B B B B ]
[ B B B B B B B B B B S B B B B B ]
[ B B B B B W W B B S W B B B B B ]
[ B B B B B W S B B W W B B B B B ]
[ B B B B B S B B B B B B B B B B ]
[ B B B B B B W B B B S B B B B B ]
[ B B B B B B B B B S W B B B B B ]
[ B B B B B B S B B B W B B B B B ]
[ B B B B B B B B B W S B B B B B ]
[ B B B B B S B B B B W B B B B B ]
[ B B B B B W W B B W S B B B B B ]
状態の総数 = 524288
3.1336355209350586

斜め跳びを許した場合の最長手数の局面は、重複解を除くと次の 4 通りになります。

  B B B B   B B B B   B B B B   B B B B  
  B S B B   B S B B   B S W B   B S W B  
  B B W B   B B B B   B B B B   B W W B  
  B B B B   B B B B   B B B B   B B B B  


        図 : 最長手数の局面

実行時間は約 3.2 秒かかりました。

●プログラムリスト１

#
# flipsquare.py : フリップ・イット・スクエア
#
#                 Copyright (C) 2022 Makoto Hiroi
#

#   盤面
#  0  1  2  3
#  4  5  6  7
#  8  9 10 11
# 12 13 14 15

# 盤面の大きさ
SIZE = 16

# 駒
S = 0
B = 1
W = 2

# 直線
line = [
    [0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15],
    [0, 4, 8, 12], [1, 5, 9, 13], [2, 6, 10, 14], [3, 7, 11, 15]
]

# 駒の跳び先表 (直線の番号, 駒の位置)
jump_table = [
    [(0, 2), (0, 3), (4, 8), (4, 12)],   # 0
    [(0, 3), (5, 9), (5, 13)],           # 1
    [(0, 0), (6, 10), (6, 14)],          # 2
    [(0, 0), (0, 1), (7, 11), (7, 15)],  # 3
    [(1, 6), (1, 7), (4, 12)],           # 4
    [(1, 7), (5, 13)],                   # 5
    [(1, 4), (6, 14)],                   # 6
    [(1, 4), (1, 5), (7, 15)],           # 7
    [(2, 10), (2, 11), (4, 0)],          # 8
    [(2, 11), (5, 1)],                   # 9
    [(2, 8), (6, 2)],                    # 10
    [(2, 8), (2, 9), (7, 3)],            # 11
    [(3, 14), (3, 15), (4, 0), (4, 4)],  # 12
    [(3, 15), (5, 1), (5, 5)],           # 13
    [(3, 12), (6, 2), (6, 6)],           # 14
    [(3, 12), (3, 13), (7, 3), (7, 7)]   # 15
]

# 駒の移動
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(n):
    start = [B] * SIZE
    start[n] = 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(n):
    start = [B] * SIZE
    start[n] = S
    dummy = [S] * SIZE
    limit = 1
    while True:
        print(f'----- {limit} -----')
        if dfs(0, limit, n, [dummy, start]):
            break
        limit += 1

# 下限値枝刈り法
def get_lower_value(b):
    lower = 0
    for i in [0, 3, 12, 15]:
        if b[i] == B: lower += 2
    return lower

def dfs1(n, limit, space, moves):
    b = moves[-1]
    if n + get_lower_value(b) > limit: return False
    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 dfs1(n + 1, limit, p, moves): return True
            moves.pop()
    return False

def solver_ids1(n):
    start = [B] * SIZE
    start[n] = S
    dummy = [S] * SIZE
    limit = get_lower_value(start)
    while True:
        print(f'----- {limit} -----')
        if dfs1(0, limit, n, [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))

●プログラムリスト２

#
# flipsquare1.py : フリップ・イット・スクエア (規則の変更)
#
#                  Copyright (C) 2022 Makoto Hiroi
#

#   盤面
#  0  1  2  3
#  4  5  6  7
#  8  9 10 11
# 12 13 14 15

# 盤面の大きさ
SIZE = 16

# 駒
S = 0
B = 1
W = 2

# 直線
line = [
    [0, 1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11], [12, 13, 14, 15],
    [0, 4, 8, 12], [1, 5, 9, 13], [2, 6, 10, 14], [3, 7, 11, 15],
    [0, 5, 10, 15], [1, 6, 11, 99], [4, 9, 14, 99],  # 追加
    [3, 6, 9, 12], [2, 5, 8, 99], [7, 10, 13, 99]    # 追加
]

# 駒の跳び先表 (直線の番号, 駒の位置)
jump_table = [
    [(0, 2), (0, 3), (4, 8), (4, 12), (8, 10), (8, 15)],   # 0
    [(0, 3), (5, 9), (5, 13), (9, 11)],           # 1
    [(0, 0), (6, 10), (6, 14), (12, 8)],          # 2
    [(0, 0), (0, 1), (7, 11), (7, 15), (11, 9), (11, 12)], # 3
    [(1, 6), (1, 7), (4, 12), (10, 14)],          # 4
    [(1, 7), (5, 13), (8, 15)],                   # 5
    [(1, 4), (6, 14), (11, 12)],                  # 6
    [(1, 4), (1, 5), (7, 15), (13, 13)],          # 7
    [(2, 10), (2, 11), (4, 0), (12, 2)],          # 8
    [(2, 11), (5, 1), (11, 3)],                   # 9
    [(2, 8), (6, 2), (8, 0)],                     # 10
    [(2, 8), (2, 9), (7, 3), (9, 1)],             # 11
    [(3, 14), (3, 15), (4, 0), (4, 4), (11, 3), (11, 6)], # 12
    [(3, 15), (5, 1), (5, 5), (13, 7)],           # 13
    [(3, 12), (6, 2), (6, 6), (10, 4)],           # 14
    [(3, 12), (3, 13), (7, 3), (7, 7), (8, 0), (8, 5)]    # 15
]

# 駒の移動
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(n):
    start = [B] * SIZE
    start[n] = 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(n):
    start = [B] * SIZE
    start[n] = S
    dummy = [S] * SIZE
    limit = 1
    while True:
        print(f'----- {limit} -----')
        if dfs(0, limit, n, [dummy, start]):
            break
        limit += 1

# 下限値枝刈り法
def get_lower_value(b):
    lower = 0
    for i in [0, 3, 12, 15]:
        if b[i] == B: lower += 2
    return lower

def dfs1(n, limit, space, moves):
    b = moves[-1]
    if n + get_lower_value(b) > limit: return False
    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 dfs1(n + 1, limit, p, moves): return True
            moves.pop()
    return False

def solver_ids1(n):
    start = [B] * SIZE
    start[n] = S
    dummy = [S] * SIZE
    limit = get_lower_value(start)
    while True:
        print(f'----- {limit} -----')
        if dfs1(0, limit, n, [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))

初版 2002 年 12 月 18 日
改訂 2022 年 11 月 5 日