ジャンプ（複数マス移動）が可能な迷路のネズミ問題をバックトラッキングで解く方法

「迷路のネズミ問題」は、バックトラッキング（探索の戻り）アルゴリズムを学ぶ上で最もよく知られた古典的な問題の一つです。この記事では、その問題に少し変化を加えたバージョンを扱います。

N×N の迷路 M が与えられ、スタート地点は左上隅の M[0, 0]、ゴール地点は右下隅の M[N – 1, N – 1] とします。ネズミはスタート地点に配置され、私たちの目標は、ネズミがスタートからゴールまで到達できる経路を見つけることです。

ここでのバリエーションは「ネズミがジャンプできる」という点です。ただし、以下の制約があります。

• ネズミは右方向または下方向にのみ移動できます。
• セルの値が 0 の場合、そのセルはブロックされており通行できません。
• 0 以外の値を持つセルは有効な経路となります。
• セル内の数字は、そのセルからネズミが最大で何マス先までジャンプできるかを示します。

アルゴリズム

ratInMaze（迷路探索の手順）

begin
    if ゴール地点に到達したら then
        解答行列を出力する
    else
        1. 現在のセルを解答行列に 1 として記録する
        2. 前方へ進むかジャンプする（最大ジャンプ値を確認）し、
           再帰的にその移動が解に至るかどうかを調べる
        3. 手順 2 の移動が正しくなかった場合は下へ移動し、
           それが解に至るかどうかを調べる
        4. 手順 2 と 3 のどちらも解にならなかった場合、
           現在のセルを 0 に戻す（バックトラック）
    end if
end

C++ 実装例

#include <iostream>
#define N 4
using namespace std;
void dispSolution(int sol[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << sol[i][j] << " ";
        cout << endl;
    }
}
bool isSafe(int maze[N][N], int x, int y) { //x,y が有効な位置かどうかを判定
    // (x, y) が迷路の範囲外なら false を返す
    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] != 0)
        return true;
    return false;
}
bool ratMazeSolve(int maze[N][N], int x, int y, int sol[N][N]) {
    if (x == N - 1 && y == N - 1) { //ゴールに到達したら true を返す
        sol[x][y] = 1;
        return true;
    }
    if (isSafe(maze, x, y)) {
        sol[x][y] = 1; //解答行列に 1 を記録
        for (int i = 1; i <= maze[x][y] && i < N; i++) {
            if (ratMazeSolve(maze, x + i, y, sol)) //右へ移動
                return true;
            if (ratMazeSolve(maze, x, y + i, sol)) //下へ移動
                return true;
        }
        sol[x][y] = 0; //解が成立しなければ 0 に戻す
        return false;
    }
    return false;
}
bool solveMaze(int maze[N][N]) {
    int sol[N][N] = { { 0, 0, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 },
        { 0, 0, 0, 0 }
    };
    if (!ratMazeSolve(maze, 0, 0, sol)) {
        cout << "Solution doesn't exist";
        return false;
    }
    dispSolution(sol);
    return true;
}
main() {
    int maze[N][N] = { { 2, 1, 0, 0 },
        { 3, 0, 0, 1 },
        { 0, 1, 0, 1 },
        { 0, 0, 0, 1 }
    };
    solveMaze(maze);
}

出力結果

1 0 0 0
1 0 0 1
0 0 0 1
0 0 0 1

コードのポイント

• isSafe 関数：指定された座標 (x, y) が迷路の範囲内かつブロックされていない（0 でない）ことを確認します。
• ratMazeSolve 関数：現在のセルから、そのセルの値の分だけ 1 マスずつ右・下へジャンプを試みます。再帰呼び出しにより全ての可能性を探索します。
• バックトラッキング：ある移動が解に至らなかった場合、そのセルを 0 に戻して別の経路を試します。これにより無駄な探索を排除しながら正しい経路を発見できます。

出力結果の行列では、1 が示されている位置が、ネズミがスタートからゴールまで通過した実際の経路を表しています。