「蛙跳びゲーム」は黒石と白石を使って遊ぶ、いわゆる「飛び石ゲーム」と呼ばれる種類のパズルです。飛び石ゲームでは、江戸時代からある「おしどりの遊び」というパズルが有名です。蛙跳びゲームは簡単そうに見えて、おしどりの遊びよりも難しいパズルです。
┌─┬─┬─┬─┬─┬─┬─┐
│●│●│●│ │○│○│○│ スタート
└─┴─┴─┴─┴─┴─┴─┘
┌─┬─┬─┬─┬─┬─┬─┐
│○│○│○│ │●│●│●│ ゴール
└─┴─┴─┴─┴─┴─┴─┘
図 : 蛙跳びゲーム
上図のように、蛙跳びゲームは黒石と白石を入れ替えることができれば成功です。石を動かす規則は次のとおりです。
石の跳び越しは次の図を参考にしてください。
┌───┐ ┌───┐
↓ │ │ ↓
┬─┬─┬─┬─┬ ┬─┬─┬─┬─┬
│ │●│○│ │ │ │●│○│ │
┴─┴─┴─┴─┴ ┴─┴─┴─┴─┴
白石の移動 黒石の移動
図 : 石の跳び越し
簡単そうに思えますが、実際にやってみると難しいのです。まず最初に、自分でパズルを解くことに挑戦してください。このパズルの難しさが実感できるでしょう。
いつものように、最短手順を求めるプログラムを作ります。コンピュータにとって、蛙跳びゲームは簡単なパズルです。単純な幅優先探索で最短手順を求めることができます。使用するプログラミング言語は Python3 (ver 3.8.10) です。
最初に石を移動して新しい盤面を生成する関数を作ります。
リスト : 石の移動
# 黒石の移動
def move_black1(board, n):
if n + 1 <= 6 and board[n] == B and board[n + 1] == S:
b = board[:]
b[n] = S
b[n + 1] = B
return b
return
def move_black2(board, n):
if n + 2 <= 6 and board[n] == B and board[n + 1] == W and board[n + 2] == S:
b = board[:]
b[n] = S
b[n + 2] = B
return b
return
# 白石の移動
def move_white1(board, n):
if n - 1 >= 0 and board[n] == W and board[n - 1] == S:
b = board[:]
b[n] = S
b[n - 1] = W
return b
return
def move_white2(board, n):
if n - 2 >= 0 and board[n] == W and board[n - 1] == B and board[n - 2] == S:
b = board[:]
b[n] = S
b[n - 2] = W
return b
return
1 が付いている関数は石を隣のマス移動し、2 が付いている関数は隣の石を跳び越して移動します。移動できない場合は None を返します。石の移動条件をそのままプログラムしただけなので、とくに難しいところはないはずです。
次は幅優先探索で解を求める関数 bfs() を作ります。
リスト : 幅優先探索
def print_answer(n, queue, prev):
if n > 0:
print_answer(prev[n], queue, prev)
print(queue[n])
def bfs(start, goal):
queue = [start]
prev = [-1]
rc = 0
while rc < len(queue):
b = queue[rc]
for i in range(7):
for move in [move_black1, move_black2, move_white1, move_white2]:
newb = move(b, i)
if not newb or newb in queue: continue
queue.append(newb)
prev.append(rc)
if newb == goal:
print_answer(len(queue) - 1, queue, prev)
return
rc += 1
def solver():
bfs([B,B,B,S,W,W,W], [W,W,W,S,B,B,B])
配列 queue と変数 rc (リードカウンタ) を使ってキューを構成します。配列 prev には 1 手前の盤面を格納している queue の添字をセットします。関数 print_answer() は queue と prev を使って移動手順を表示します。
あとは単純な幅優先探索です。キューから盤面 b を取り出したら、石を移動する関数 move() に渡して新しい盤面 newb を生成します。newb が queue に無ければ、newb を queue に、rc を prev に追加します。newb が goal と等しければ、print_answer() で手順を表示して return で探索を終了します。
それでは実行結果を示します。移動する石を太字で表しています。
>>> solver() [1, 1, 1, 0, 2, 2, 2] [1, 1, 0, 1, 2, 2, 2] [1, 1, 2, 1, 0, 2, 2] [1, 1, 2, 1, 2, 0, 2] [1, 1, 2, 0, 2, 1, 2] [1, 0, 2, 1, 2, 1, 2] [0, 1, 2, 1, 2, 1, 2] [2, 1, 0, 1, 2, 1, 2] [2, 1, 2, 1, 0, 1, 2] [2, 1, 2, 1, 2, 1, 0] [2, 1, 2, 1, 2, 0, 1] [2, 1, 2, 0, 2, 1, 1] [2, 0, 2, 1, 2, 1, 1] [2, 2, 0, 1, 2, 1, 1] [2, 2, 2, 1, 0, 1, 1] [2, 2, 2, 0, 1, 1, 1]
15 手で解くことができました。この手順は黒石から動かしていますが、白石から動かしても解くことができます。
ところで、今回はアルゴリズムに幅優先探索を使いましたが、黒石と白石は後戻りできないことから、バックトラックでも簡単に最短手順を求めることができます。興味のある方は、実際に試してみるといいでしょう。
石の移動は、違う色の石を跳び越すか、隣の空いている場所へひとつ移動するという 2 通りの方法があります。まず、跳び越す回数を求めましょう。ひとつの黒石に注目してください。この石は白石を跳び越すか、または白石に跳び越されることになります。どちらにしても、この黒石には白石の数だけ跳び越しが行われます。
したがって、n 個ずつの石がある場合、ひとつの黒石が右側へ移動する間に跳び越しは n 回行われることになります。黒石は n 個ありますから、跳び越す回数は全部で n 2 回となります。
次は、石をひとつ移動する回数を求めます。石が n 個ずつある場合、各石の移動距離は n + 1 なので、合計では 2n(n + 1) になります。この値から跳び越しによる移動距離を引けば、石をひとつ移動する回数を求めることができます。
したがって、石の移動回数は次のようになります。
石が 3 個ずつの場合は 3 * 3 + 2 * 3 = 15 回、4 個ずつの場合は 4 * 4 + 2 * 4 = 24 回、とあっていますね。簡単に説明しましたが、詳しいことは参考文献『数理パズルのはなし』を参考にしてください。
ところで、このドキュメントでは「最短手数」と書きましたが、これより長い手順はありません。つまり、蛙跳びゲームは、この回数でないと解けないのです。
次は、蛙跳びゲームを平面に拡張してみましょう。それでは問題です。
┌─┐ ┌─┬─┐ ┌─┬─┬─┐
│●│ │●│●│ │●│●│●│
┌─┼─┤ ├─┼─┤ ├─┼─┼─┤
│●│●│ │●│●│ │●│●│●│
┌─┼─┼─┼─┬─┐ ├─┼─┼─┐ ├─┼─┼─┼─┬─┐
│●│●│ │○│○│ │●│ │○│ │●│●│ │○│○│
└─┴─┼─┼─┼─┘ └─┼─┼─┤ └─┴─┼─┼─┼─┤
│○│○│ │○│○│ │○│○│○│
├─┼─┘ ├─┼─┤ ├─┼─┼─┤
│○│ │○│○│ │○│○│○│
└─┘ └─┴─┘ └─┴─┴─┘
（Ａ） （Ｂ） （Ｃ）
問題 : 平面上の蛙跳びゲーム
黒石と白石を入れ替えるのがパズルの目的です。石を動かす規則は次のとおりです。
この規則で黒石と白石を入れ替える最短手順を求めてください。
問題 (A) と (B) は「旧 Common Lisp 入門」の「蛙跳びゲームを解く」で取り上げました。そこで、今回は問題 (C) の解法プログラムを Python3 で作成します。
今回は幅優先探索でプログラムを作ります。最初に局面の総数を求めます。マスは全部で 17 か所あるので、空き場所の配置は 17 通りあります。石の配置は、残り 16 か所に 8 個の黒石を配置するので 16Ｃ8 = 12870 通りあります。局面の総数は 17 * 12870 = 218790 通りとなります。キューは Python の標準ライブラリ collections の deque を、同一局面のチェックは辞書を使うことにします。
最初にデータ構造を定義します。盤面は 1 次元配列で表して、黒石を B (1), 白石を W (2), 空き場所を S (0) で表します。盤面と配列の対応は下図を見てください。
┌─┬─┬─┐
│０│１│２│
├─┼─┼─┤
│３│４│５│
├─┼─┼─┼─┬─┐
│６│７│８│９│10│
└─┴─┼─┼─┼─┤
│11│12│13│
├─┼─┼─┤
│14│15│16│
└─┴─┴─┘
図 : 盤面
石の移動方向を番号の大小関係でチェックするため、番号は左上から右下へ順番につけています。こうすると、黒石の移動は小さな番号から大きな番号、逆に白石の移動は大きな番号から小さな番号になります。
石の移動は「隣接リスト」と「跳び先表」を用意すると簡単にプログラムできます。次のリストを見てください。
リスト : 隣接リスト
neighbor = [
[1, 3], # 0
[0, 2, 4], # 1
[1, 5], # 2
[0, 4, 6], # 3
[1, 3, 5, 7], # 4
[2, 4, 8], # 5
[3, 7], # 6
[4, 6, 8], # 7
[5, 7, 9, 11], # 8
[8, 10, 12], # 9
[9, 13], # 10
[8, 12, 14], # 11
[9, 11, 13, 15], # 12
[10, 12, 16], # 13
[11, 15], # 14
[12, 14, 16], # 15
[13, 15] # 16
]
リスト : 跳び先表
jump_table = [
[(1, 2), (3, 6)], # 0
[(4, 7)], # 1
[(1, 0), (5, 8)], # 2
[(4, 5)], # 3
[], # 4
[(4, 3), (8, 11)], # 5
[(3, 0), (7, 8)], # 6
[(4, 1), (8, 9)], # 7
[(5, 2), (7, 6), (9, 10), (11, 14)], # 8
[(8, 7), (12, 15)], # 9
[(9, 8), (13, 16)], # 10
[(8, 5), (12, 13)], # 11
[], # 12
[(12, 11)], # 13
[(11, 8), (15, 16)], # 14
[(12, 9)], # 15
[(13, 10), (15, 14)] # 16
]
跳び先表 jump_table は空き場所を基準にして、跳び越される石の位置と跳ぶ石の位置をタプルにまとめたものです。たとえば、空き場所が 0 番の場合、2 番の石が 1 番の石を跳び越して 0 番へ移動することができます。このとき、石の種類をチェックすることをお忘れなく。
次は指し手を生成する関数 make_move() を作ります。次のリストを見てください。
リスト : 指し手の生成
# 移動可能か
def is_move(board, n, s):
if board[n] == B:
return n < s
else:
return n > s
# 指し手の生成
def make_move(board, s):
move = []
for i in neighbor[s]:
if is_move(board, i, s): move.append(i)
for i, j in jump_table[s]:
if board[i] != board[j] and is_move(board, j, s):
move.append(j)
return move
関数 make_move() の引数 board が盤面、s が空き場所の位置を表します。関数 is_move() は石の移動方向をチェックして、移動できるならば True を返します。生成した指し手は配列 move に格納します。
最初の for ループで、隣の空き場所へ石を移動する場合をチェックします。隣接リスト neighbor から空き場所の隣の位置を取り出して変数 i にセットします。あとは is_move() で移動方向をチェックするだけです。移動できる場合は、移動する石の位置 i を配列 move に追加します。
次の for ループで、他の石を跳び越して移動する場合をチェックします。跳び先表 jump_table から跳び越される石の位置と跳ぶ石の位置を取り出して、変数 i と j にセットします。board[i] と board[j] の値が異なっていて、is_move() が真であれば j から s へ跳び越すことができます。配列 move に j をセットします。最後に move を返します。
あとは単純な幅優先探索です。配列 move から指し手を取り出し、石を移動して新しい局面を生成します。生成した局面は辞書でチェックして、同一局面がなければキューに登録します。これらの処理は簡単なので説明は省略いたします。詳細はプログラムリストをお読みください。
それでは実行結果を示します。
>>> s = time.time(); solver1(); print(time.time() - s)
(1, 1, 1, 1, 1, 1, 1, 1, 0, 2, 2, 2, 2, 2, 2, 2, 2)
(1, 1, 1, 1, 1, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2)
・・・省略・・・
(2, 2, 2, 2, 2, 2, 2, 2, 1, 0, 1, 1, 1, 1, 1, 1, 1)
(2, 2, 2, 2, 2, 2, 2, 2, 0, 1, 1, 1, 1, 1, 1, 1, 1)
133864
0.41406965255737305
実行環境 : Python3 (ver 3.8.10), Ubunts 20.04 (WSL1), Intel Core i5-6200U 2.30GHz
[0] [1] [2] [3] [4] [5] [6] [7]
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 0 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2
1 1 0 2 2 1 1 1 2 2 1 1 1 2 2 1 1 0 2 2 1 0 1 2 2 1 2 1 0 2 1 2 1 2 0 1 2 0 2 1
2 2 2 2 2 2 0 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
[8] [9] [10] [11] [12] [13] [14] [15]
1 1 0 1 0 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1
1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2
1 2 1 2 1 1 2 1 2 1 1 0 1 2 1 1 2 1 0 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 0 2 1
1 2 2 1 2 2 1 2 2 1 2 2 1 0 2 0 1 2 2 1 2 2 1 2
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 0 2 2 1 2 2
[16] [17] [18] [19] [20] [21] [22] [23]
1 2 0 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2
1 1 2 1 1 0 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2
1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 0 1 2 0 2 1 0 2 1 2 1
2 1 2 2 1 2 0 1 2 2 1 0 2 1 2 2 1 2 2 1 2 2 1 2
1 2 2 1 2 2 1 2 2 1 2 2 1 2 0 1 2 1 1 2 1 1 2 1
[24] [25] [26] [27] [28] [29] [30] [31]
1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 0 2 2
0 1 2 2 1 0 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2
1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 0 1 2 0 2 1 0 2 1 2 1 1 2 1 2 1
2 1 2 2 1 2 0 1 2 2 1 0 2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1
[32] [33] [34] [35] [36] [37] [38] [39]
2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2 2 1 2
1 2 1 2 1 1 0 1 2 1 1 2 1 0 1 1 2 1 2 1 1 2 1 2 1 1 2 0 2 1 0 2 1 2 1 2 0 1 2 1
2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1 2 1 1
1 2 1 1 2 1 1 2 1 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1
[40] [41] [42] [43] [44] [45] [46]
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 0 2 2 2 0 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
2 1 1 2 1 2 1 1 2 1 2 1 1 2 1 2 1 0 2 1 2 0 1 2 1 2 2 1 0 1 2 2 0 1 1
2 1 1 2 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
最短手数は 46 手になりました。実行時間ですが、Python3 でも 1 秒かからずに解くことができました。PyPy3 を使うともっと速くなるかもしれません。興味のある方は試してみてください。ご参考までに、問題 (A) と (B) の解答を示します。
次は、蛙跳びゲームの盤面を小さくしてみましょう。下図を見てください。
┌─┬─┐
│●│●│
├─┼─┼─┐
│●│ │○│
└─┼─┼─┤
│○│○│
└─┴─┘
図 : 蛙跳びゲーム
黒石と白石が 3 個ずつあります。この場合、今までの規則では黒石と白石を入れ替えることができません。そこで、規則を次のように変更します。
規則 1 と 2 で、黒石と白石を入れ替える最短手順を求めてください。出典は参考文献『ゲームにひそむ数理』と『ブルーバックス B-1377 超々難問数理パズル 解けるものなら解いてごらん』です。後者には規則 2 の問題が掲載されています。そこで、今回は新しい規則 1 を追加してみました。ちなみに、規則 1 の方が簡単に解けます。
それではプログラムを作りましょう。この問題は局面の総数が 140 通りしかないので、同一局面のチェックは線形探索で十分です。あとは、隣接リストと跳び先表を修正するだけです。
リスト : 規則１
neighbor21 = [
[1, 2, 3], # 0
[0, 2, 3, 4], # 1
[0, 1, 3, 5], # 2
[0, 1, 2, 4, 5, 6], # 3
[1, 3, 5, 6], # 4
[2, 3, 4, 6], # 5
[3, 4, 5] # 6
]
jump_table21 = [
[(3, 6)], # 0
[(3, 5)], # 1
[(3, 4)], # 2
[], # 3
[(3, 2)], # 4
[(3, 1)], # 5
[(3, 0)] # 6
];
リスト : 規則２
neighbor22 = [
[1, 2], # 0
[0, 3], # 1
[0, 3], # 2
[1, 2, 4, 5], # 3
[3, 6], # 4
[3, 6], # 5
[4, 5], # 6
];
jump_table22 = [
[], # 0
[(3, 5)], # 1
[(3, 4)], # 2
[], # 3
[(3, 2)], # 4
[(3, 1)], # 5
[] # 6
]
規則 1 は斜め跳びができるので、隣接リストと跳び先表のデータ数は規則 2 よりも多くなります。それから、規則 2 では後戻りができるので、関数 is_move() によるチェックが不要になります。詳細はプログラムリストをお読みください。
それでは実行結果を示します。規則１の最短手数は 8 手になります。
>>> solver21() [1, 1, 1, 0, 2, 2, 2] [0, 1, 1, 1, 2, 2, 2] [2, 1, 1, 1, 2, 2, 0] [2, 1, 1, 0, 2, 2, 1] [2, 0, 1, 1, 2, 2, 1] [2, 2, 1, 1, 2, 0, 1] [2, 2, 0, 1, 2, 1, 1] [2, 2, 2, 1, 0, 1, 1] [2, 2, 2, 0, 1, 1, 1]
[0]
1 1
1 0 2
2 2
[1] [2] [3] [4] [5] [6] [7] [8]
0 1 2 1 2 1 2 0 2 2 2 2 2 2 2 2
1 1 2 1 1 2 1 0 2 1 1 2 1 1 2 0 1 2 2 1 0 2 0 1
2 2 2 0 2 1 2 1 0 1 1 1 1 1 1 1
後戻りを許す規則 2 の場合、最短手数は 15 手になります。
>>> solver22() [1, 1, 1, 0, 2, 2, 2] [1, 0, 1, 1, 2, 2, 2] [1, 2, 1, 1, 2, 0, 2] [1, 2, 1, 0, 2, 1, 2] [1, 2, 0, 1, 2, 1, 2] [0, 2, 1, 1, 2, 1, 2] [2, 0, 1, 1, 2, 1, 2] [2, 1, 1, 0, 2, 1, 2] [2, 1, 1, 2, 0, 1, 2] [2, 1, 1, 2, 2, 1, 0] [2, 1, 1, 2, 2, 0, 1] [2, 0, 1, 2, 2, 1, 1] [2, 2, 1, 0, 2, 1, 1] [2, 2, 0, 1, 2, 1, 1] [2, 2, 2, 1, 0, 1, 1] [2, 2, 2, 0, 1, 1, 1]
[0] [1] [2] [3] [4] [5] [6] [7]
1 1 1 0 1 2 1 2 1 2 0 2 2 0 2 1
1 0 2 1 1 2 1 1 2 1 0 2 0 1 2 1 1 2 1 1 2 1 0 2
2 2 2 2 0 2 1 2 1 2 1 2 1 2 1 2
[8] [9] [10] [11] [12] [13] [14] [15]
2 1 2 1 2 1 2 0 2 2 2 2 2 2 2 2
1 2 0 1 2 2 1 2 2 1 2 2 1 0 2 0 1 2 2 1 0 2 0 1
1 2 1 0 0 1 1 1 1 1 1 1 1 1 1 1
[6] -> [7] で、黒石 (1) が後戻りしています。
今回は幅優先探索で解きましたが、「反復深化」でも簡単に解くことができると思います。興味のある方は挑戦してみてください。
#
# kaeru.py : 蛙跳びゲーム
#
# Copyright (C) 2022 Makoto Hiroi
#
import time
from collections import deque
# 駒
S = 0
B = 1
W = 2
# [B, B, B, S, W, W, W]
# 黒石の移動
def move_black1(board, n):
if n + 1 <= 6 and board[n] == B and board[n + 1] == S:
b = board[:]
b[n] = S
b[n + 1] = B
return b
return
def move_black2(board, n):
if n + 2 <= 6 and board[n] == B and board[n + 1] == W and board[n + 2] == S:
b = board[:]
b[n] = S
b[n + 2] = B
return b
return
# 白石の移動
def move_white1(board, n):
if n - 1 >= 0 and board[n] == W and board[n - 1] == S:
b = board[:]
b[n] = S
b[n - 1] = W
return b
return
def move_white2(board, n):
if n - 2 >= 0 and board[n] == W and board[n - 1] == B and board[n - 2] == S:
b = board[:]
b[n] = S
b[n - 2] = W
return b
return
def print_answer(n, queue, prev):
if n > 0:
print_answer(prev[n], queue, prev)
print(queue[n])
def bfs(start, goal):
queue = [start]
prev = [-1]
rc = 0
while rc < len(queue):
b = queue[rc]
for i in range(7):
for move in [move_black1, move_black2, move_white1, move_white2]:
newb = move(b, i)
if not newb or newb in queue: continue
queue.append(newb)
prev.append(rc)
if newb == goal:
print_answer(len(queue) - 1, queue, prev)
return
rc += 1
def solver():
bfs([B,B,B,S,W,W,W], [W,W,W,S,B,B,B])
#
# 平面上の蛙跳びゲーム
#
# 隣接リスト
neighbor = [
[1, 3], # 0
[0, 2, 4], # 1
[1, 5], # 2
[0, 4, 6], # 3
[1, 3, 5, 7], # 4
[2, 4, 8], # 5
[3, 7], # 6
[4, 6, 8], # 7
[5, 7, 9, 11], # 8
[8, 10, 12], # 9
[9, 13], # 10
[8, 12, 14], # 11
[9, 11, 13, 15], # 12
[10, 12, 16], # 13
[11, 15], # 14
[12, 14, 16], # 15
[13, 15] # 16
]
# 跳び先表
jump_table = [
[(1, 2), (3, 6)], # 0
[(4, 7)], # 1
[(1, 0), (5, 8)], # 2
[(4, 5)], # 3
[], # 4
[(4, 3), (8, 11)], # 5
[(3, 0), (7, 8)], # 6
[(4, 1), (8, 9)], # 7
[(5, 2), (7, 6), (9, 10), (11, 14)], # 8
[(8, 7), (12, 15)], # 9
[(9, 8), (13, 16)], # 10
[(8, 5), (12, 13)], # 11
[], # 12
[(12, 11)], # 13
[(11, 8), (15, 16)], # 14
[(12, 9)], # 15
[(13, 10), (15, 14)] # 16
]
# 移動可能か
def is_move(board, n, s):
if board[n] == B:
return n < s
else:
return n > s
# 指し手の生成
def make_move(board, s):
move = []
for i in neighbor[s]:
if is_move(board, i, s): move.append(i)
for i, j in jump_table[s]:
if board[i] != board[j] and is_move(board, j, s):
move.append(j)
return move
# 手順の表示
def print_answer1(b, table):
prev = table[b]
if prev:
print_answer1(prev, table)
print(b)
# 幅優先探索
def bfs1(start, goal):
queue = deque()
queue.append((start, start.index(0)))
check = {}
check[start] = []
while len(queue) > 0:
b, s = queue.popleft()
for i in make_move(b, s):
a = list(b)
a[s] = a[i]
a[i] = S
newb = tuple(a)
if newb in check: continue
queue.append((newb, i))
check[newb] = b
if newb == goal:
print_answer1(newb, check)
print(len(check))
return
def solver1():
bfs1(tuple([B,B,B,B,B,B,B,B,S,W,W,W,W,W,W,W,W]),
tuple([W,W,W,W,W,W,W,W,S,B,B,B,B,B,B,B,B]))
#
# 平面上の蛙跳びゲーム２
#
# 規則１
neighbor21 = [
[1, 2, 3], # 0
[0, 2, 3, 4], # 1
[0, 1, 3, 5], # 2
[0, 1, 2, 4, 5, 6], # 3
[1, 3, 5, 6], # 4
[2, 3, 4, 6], # 5
[3, 4, 5] # 6
]
jump_table21 = [
[(3, 6)], # 0
[(3, 5)], # 1
[(3, 4)], # 2
[], # 3
[(3, 2)], # 4
[(3, 1)], # 5
[(3, 0)] # 6
];
# 規則２
neighbor22 = [
[1, 2], # 0
[0, 3], # 1
[0, 3], # 2
[1, 2, 4, 5], # 3
[3, 6], # 4
[3, 6], # 5
[4, 5], # 6
];
jump_table22 = [
[], # 0
[(3, 5)], # 1
[(3, 4)], # 2
[], # 3
[(3, 2)], # 4
[(3, 1)], # 5
[] # 6
]
# 指し手の生成
def make_move21(board, s):
move = []
for i in neighbor21[s]:
if is_move(board, i, s): move.append(i)
for i, j in jump_table21[s]:
if board[i] != board[j] and is_move(board, j, s):
move.append(j)
return move
def make_move22(board, s):
move = []
for i in neighbor22[s]: move.append(i)
for i, j in jump_table22[s]:
if board[i] != board[j]: move.append(j)
return move
# 手順の表示
def print_answer2(n, queue):
if n > 0:
print_answer2(queue[n][1], queue)
print(queue[n][0])
# 幅優先探索
def bfs2(start, goal, mover = make_move21):
queue = [(start, -1, start.index(0))]
check = [start]
rc = 0
while rc < len(queue):
b, _, s = queue[rc]
for i in mover(b, s):
newb = b[:]
newb[s] = newb[i]
newb[i] = S
if newb in check: continue
queue.append((newb, rc, i))
check.append(newb)
if newb == goal:
print_answer2(len(queue) - 1, queue)
return
rc += 1
def solver21():
bfs2([B,B,B,S,W,W,W], [W,W,W,S,B,B,B])
def solver22():
bfs2([B,B,B,S,W,W,W], [W,W,W,S,B,B,B], make_move22)
0:
B
B B
B B S W W
W W
W
1: 2: 3: 4: 5: 6:
B B B B B B
B B B S B W B W B W B W
B B W W W B B W W W B B S W W B B W S W B S W B W S B W B W
S W B W B W B W B W B W
W W W W W W
7: 8: 9: 10: 11: 12:
B B B B B B
B W B W B W B W B W B W
W B S B W W B W B W W B W B W W B W B W W B W S W W S W B W
B W B W S W W S W B W B
W S B B B B
13: 14: 15: 16: 17: 18:
B B B B B B
S W W S W W W W W W W W
W B W B W W B W B W W B S B W W B W B S W B W S B W S W B B
W B W B W B W B W B W B
B B B B B B
19: 20: 21: 22: 23:
B S W W W
W W W W W S W W W W
W W S B B W W B B B W W B B B W W B B B W W S B B
W B W B W B S B B B
B B B B B
図：問題 (A) の解答 (23 手)
0:
B B
B B
B S W
W W
W W
1: 2: 3: 4: 5: 6: 7: 8:
B B B B B S B W B W B W B W B W
B B B S B B B B B B B B B B B B
B W W B W W B W W B S W B W S S W B W S B W W B
S W B W B W B W B W B W B W B W
W W W W W W W W W W W W W W S W
9: 10: 11: 12: 13: 14: 15: 16:
B W B W B W B W B W B W S W W S
B B B B B B B B B S S B B B B B
W W B W W S W W W W W W W W W W W W W W W W W W
B W B W B S S B B B B B B B B B
W S W B W B W B W B W B W B W B
17: 18: 19: 20: 21: 22: 23: 24:
W W W W W W W W W W W W W W W W
B B B S S B W B W B W B W B W B
W S W W B W W B W S B W W B S W S B W W B W W B
B B B B B B B B B B B B B B S B
W B W B W B W B W B W B S B B B
25: 26:
W W W W
W S W W
W W B W S B
B B B B
B B B B
図：問題 (B) の解答 (26 手)