蛇はしごゲーム（Snake and Ladder）の最短到達手数を求めるアルゴリズム

蛇はしごゲームとは

蛇はしごゲーム（Snakes and Ladders）は、世界中で親しまれている有名なボードゲームです。ボード上には番号が振られたマスが並んでおり、一部のマス同士は「はしご」または「ヘビ」によって接続されています。はしごのあるマスに止まれば、順番に進むことなく一気に上のマスへ移動でき、ゴールに大きく近づくことができます。一方、ヘビのいるマスに止まってしまうと、下のマスへ引き戻され、そこから再びスタートすることになります。

本記事では、この問題に対してスタートからゴールまで到達するために必要な最小のサイコロ振り回数を求めるアルゴリズムを解説します。最短手数を求める場合、幅優先探索（BFS）が非常に有効です。

入力と出力の例

入力：ヘビとはしごの始点・終点の位置
ヘビ：26 → 0、20 → 8、16 → 3、18 → 6
はしご：2 → 21、4 → 7、10 → 25、19 → 28

出力：
Min Dice throws required is 3（最小のサイコロ振り回数は3回）

アルゴリズム（幅優先探索）

各マスをグラフの頂点とみなし、サイコロを1回振ることで最大6つ先のマスへ移動できることを辺と考えると、この問題は頂点0から頂点cell-1までの最短経路問題として扱えます。すべての辺の重みが等しいため、幅優先探索（BFS）を使えば最短距離（＝最小のサイコロ振り回数）を効率よく求められます。

関数シグネチャは以下のとおりです。

minDiceThrow(move, cell)

入力： ヘビやはしごのジャンプ先を格納した配列 move、およびマスの総数 cell
出力： 最後のマスに到達するまでに必要な最小のサイコロ振り回数

処理の手順

1. すべてのマスを「未訪問」として初期化する。
2. キューを用意し、開始マス（頂点番号0、距離0）を訪問済みとして登録する。
3. キューが空になるまで以下を繰り返す。
   • キューの先頭要素を取り出し、その頂点番号 v を確認する。
   • v が最後のマス（cell - 1）であればループを抜ける。
   • v + 1 から v + 6 まで（かつ cell 未満）の各マス j について、未訪問なら距離を現在の距離＋1として設定し、訪問済みにする。
   • j の位置にヘビまたははしごがある場合（move[j] != -1）、ジャンプ先 move[j] を次の頂点とする。なければ j 自身を次の頂点としてキューに追加する。
4. 最後に取り出した頂点の距離を結果として返す。

C++による実装例

#include<iostream>
#include <queue>
using namespace std;

struct vertex {
    int vert;
    int dist;      // ソースからの距離（サイコロを振った回数）
};

int minDiceThrow(int move[], int cell) {
    bool visited[cell];
    for (int i = 0; i < cell; i++)
        visited[i] = false;     // 初期状態ではすべてのマスは未訪問

    queue<vertex> q;

    visited[0] = true;          // マス0から開始
    vertex s = {0, 0};
    q.push(s);                  // 頂点0をキューに追加

    vertex qVert;
    while (!q.empty()) {
        qVert = q.front();
        int v = qVert.vert;

        if (v == cell-1)        // v がゴールの頂点なら終了
            break;

        q.pop();
        // サイコロの出目1〜6で移動できる範囲を調べる
        for (int j=v+1; j<=(v+6) && j<cell; ++j) {
            if (!visited[j]) {
                vertex newVert;
                newVert.dist = (qVert.dist + 1);   // 距離を+1
                visited[j] = true;

                if (move[j] != -1)
                    newVert.vert = move[j];        // ヘビまたははしごでジャンプ
                else
                    newVert.vert = j;
                q.push(newVert);
            }
        }
    }
    return qVert.dist;          // 最小のサイコロ振り回数
}

int main() {
    int cell = 30;              // 盤面は30マスとする
    int moves[cell];

    for (int i = 0; i<cell; i++)
        moves[i] = -1;          // 初期状態ではヘビもはしごもなし

    // マス i のはしごは moves[i] へジャンプ
    moves[2] = 21;
    moves[4] = 7;
    moves[10] = 25;
    moves[19] = 28;

    // マス i のヘビは moves[i] へジャンプ
    moves[26] = 0;
    moves[20] = 8;
    moves[16] = 3;
    moves[18] = 6;

    cout << "Min Dice throws required is " << minDiceThrow(moves, cell);
}

実行結果

Min Dice throws required is 3

まとめ

蛇はしごゲームの最短クリア手数問題は、盤面をグラフとしてモデル化し、幅優先探索（BFS）を適用することで解けます。計算量はマス数を N とすると O(N) となり、各マスは高々一度しか訪問しないため非常に効率的です。サイコロの出目1〜6で到達可能なマスを順に探索し、ヘビやはしごによるジャンプを辺の張り替えとして扱う点がこのアルゴリズムのポイントです。