ラット迷路問題とは？バックトラッキングによる解法をC++で解説

この記事では、アルゴリズムの学習で定番となる「ラット迷路問題（Rat in a Maze）」について、問題の概要からバックトラッキングを使った解法、C++による実装例までをわかりやすく解説します。

問題の概要

N × N のサイズの迷路が与えられます。スタート地点は左上のセル、ゴール地点は右下のセルです。迷路には移動可能なセルと、通行止め（ブロックされた）セルが混在しています。

ラットがスタート地点からゴール地点へ向かって移動するとき、「ゴールまでたどり着ける経路が存在するか」を判定し、存在する場合はその正しい経路をマークして出力するのがこの問題の目的です。

迷路は二値マトリクス（0 と 1 のみで構成される行列）として表現されます。

• 1 … 移動可能な通路
• 0 … 壁またはブロックされた領域

注意： ラットが移動できる方向は「右」と「下」の2方向のみに制限されています。

入力と出力

入力：
このアルゴリズムでは、迷路を行列（マトリクス）として受け取ります。
行列内の値 1 は自由に通れる空間を、0 は壁やブロックされた領域を表します。

（図：左上の丸がスタート地点、右下の丸がゴール地点を示します）

出力：
行列形式で結果を出力します。この行列から、ラットがゴール地点へ到達するための経路を読み取ることができます。

アルゴリズム

解法の中心となるのは、バックトラッキング（探索の巻き戻し）です。まず、ある座標が移動可能かどうかを判定する関数 isValid(x, y) を定義します。

isValid(x, y)

入力： 迷路上の座標 x, y
出力： 座標 (x, y) が有効なら true、そうでなければ false

Begin
    if x と y が範囲内であり、(x,y) の場所がブロックされていなければ
        return true
    return false
End

solveRatMaze(x, y)

入力： スタート地点の座標 x, y
出力： ゴールまでの経路。到達できない場合は false

Begin
    if (x,y) が右下の角（ゴール）であれば
        その場所を 1 としてマークする
        return true
    if isValidPlace(x, y) = true であれば
        (x, y) を 1 としてマークする
        if solveRatMaze(x+1, y) = true ならば   // 右方向への移動
            return true
        if solveRatMaze(x, y+1) = true ならば   // 下方向への移動
            return true
        バックトラック時には (x,y) を 0 に戻す
        return false
    return false
End

このように、進める間は再帰的に探索を進め、行き詰まったら直前の分岐点まで戻って別のルートを試す、というのがバックトラッキングの基本的な流れです。

C++による実装例

#include<iostream>
#define N 5
using namespace std;

int maze[N][N] = {
    {1, 0, 0, 0, 0},
    {1, 1, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {0, 0, 0, 1, 0},
    {1, 1, 1, 1, 1}
};

int sol[N][N];   // 最終的な迷路の経路（解答）を格納する配列

void showPath() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << sol[i][j] << " ";
        cout << endl;
    }
}

// 座標が迷路の範囲内かつ値が 1（通路）であるかを判定する関数
bool isValidPlace(int x, int y) {
    if(x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1)
        return true;
    return false;
}

bool solveRatMaze(int x, int y) {
    if(x == N-1 && y == N-1) {      // (x,y) が右下の部屋（ゴール）の場合
        sol[x][y] = 1;
        return true;
    }

    if(isValidPlace(x, y) == true) {   // (x,y) が有効な場所かどうかを確認
        sol[x][y] = 1;                 // 有効な場所なら 1 をセット
        if (solveRatMaze(x+1, y) == true)     // 右方向へ進んで経路を探す
            return true;
        if (solveRatMaze(x, y+1) == true)     // x 方向が塞がれていれば下方向へ
            return true;
        sol[x][y] = 0;                 // 両方とも行き止まりなら経路なし
        return false;
    }
    return false;
}

bool findSolution() {
    if(solveRatMaze(0, 0) == false) {
        cout << "There is no path";
        return false;
    }
    showPath();
    return true;
}

int main() {
    findSolution();
}

実行結果

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

出力された行列において、1 が立っているセルをつなぐと、それがラットが通るべき正しい経路になります。左上から右下へ、1 のセルをたどることでゴールまで到達できることが確認できます。

まとめ

ラット迷路問題は、バックトラッキングの考え方を学ぶうえで最も基本的な題材の一つです。「とりあえず進んでみて、ダメなら戻って別の道を試す」というシンプルな発想が、多くの探索問題に応用できます。ぜひコードを実際に動かして、挙動を確かめてみてください。