Pythonで蛇と梯子ゲームの最短手数を求める方法｜BFSを使った実装例

「蛇と梯子（Snakes and Ladders）」は、サイコロを振ってマスを進み、梯子に掛かれば一気に上へ、蛇にかまれれば下へ戻される古典的なボードゲームです。本記事では、このゲームをPythonで解き、ゴールであるマス100に到達するまでに必要な最小のサイコロ振り回数を求めるプログラムを紹介します。

問題の概要

ここでは特別なルールとして、サイコロの出目を1〜6の中から自由に選べるものとします。スタート地点はマス0、目的地はマス100です。盤面上の蛇と梯子の位置情報が与えられたとき、目的地に到達するために必要な最小のダイスロール回数を求めます。

配列 snakes と ladders は、それぞれ盤面上の蛇と梯子の位置を表します。各要素は「始点と終点」のペアで構成されており、梯子の場合は始点から終点へ進み、蛇の場合は始点から終点へ後退します。

入力例

ladders = [(11, 40), (37, 67), (47, 73), (15, 72)]、snakes = [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)] の場合、出力は 8 になります。

つまり、この梯子と蛇の配置のもとでは、マス100に到達するために最低8回の移動が必要だということです。

解き方のアプローチ

この問題はグラフの最短経路問題として捉えることができます。各ターンで最大6通りの進み方があるため、幅優先探索（BFS）の考え方を使うことで、最短手数を効率的に求められます。具体的な手順は以下の通りです。

• 配列 snakes を配列 ladders に連結する
• 辞書 edges を新しく作成し、各ペア (f, t) に対して edges[f] = t を設定する
• 訪問済みを記録する集合 u と、現在のレベルの位置を保持する集合 v を作成する
• v に初期位置 1 を追加し、カウンタ m を 0 で初期化する
• v に 100 が含まれない間、以下を繰り返す：
  • m を 1 増やし、新しい集合 w を作成する
  • v 内の各位置 f について、i を 1〜6 の範囲で動かしながら次の位置 n = f + i を計算する
  • n が edges に存在すれば、梯子または蛇の効果で n を edges[n] に置き換える
  • n がすでに u に存在すればスキップし、そうでなければ n を u と w に追加する
  • ループ終了後、v = w と更新して次のターンへ進む
• ループを抜けたら m を返す

BFSでは各ループの反復が「1回のサイコロ振り」に対応するため、マス100が初めて現れた時点の手数 m がそのまま最短手数になります。

実装例

それでは、実際のPythonコードを見てみましょう。

def solve(ladders, snakes):
    ladders.extend(snakes)
    edges = {}
    for f, t in ladders:
        edges[f] = t
    u = set()
    v = set()
    v.add(1)
    m = 0
    while 100 not in v:
        m += 1
        w = set()
        for f in v:
            for i in range(1, 7):
                n = f + i
                if n in edges:
                    n = edges[n]
                if n in u:
                    continue
                u.add(n)
                w.add(n)
        v = w
    return m

print(solve([(11, 40), (37, 67), (47, 73), (15, 72)],
            [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]))

入力

[(11, 40), (37,67),(47, 73),(15, 72)], [(90, 12), (98, 31), (85, 23), (75, 42), (70, 18), (49, 47)]

出力

8

このように、幅優先探索を活用することで、蛇と梯子ゲームのような盤面ゲームの最短手数をシンプルかつ効率的に計算できます。アルゴリズムの計算量は盤面のマス数にほぼ比例するため、100マス程度の盤面であれば瞬時に答えが得られます。