C++で数字迷路のコーナーセルから中央セルへの全経路を探索する方法

数値が埋め込まれた正方形の迷路を考えます。この迷路において、四隅のセル(コーナーセル)から中央のセル(ミドルセル)までのすべての経路を見つけることが目的です。

移動のルールは次のとおりです。あるセル [i, j] に書かれた値を n とすると、上下左右の4方向にちょうど n ステップ進む必要があります。つまり、[i+n, j]、[i-n, j]、[i, j+n]、[i, j-n] のいずれかのセルへ移動できます。移動先が迷路の範囲外になる場合は、その方向には進めません。

入力例

以下のような 9×9 の迷路が与えられたとします。

出力例

この場合、出力は次のようになります。

• (0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5, 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(5, 1)→(0, 1)→(4, 1)→(4, 4)→MIDDLE
• (0, 0)→(0, 3)→(0, 7)→(6, 7)→(6, 3)→(3, 3)→(3, 4)→(5, 4)→(5, 2)→(1, 2)→(1, 7)→(7, 7)→(7, 1)→(2, 1)→(2, 4)→(4, 4)→MIDDLE
• (0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(7, 1)→(2, 1)→(2, 4)→(4, 4)→MIDDLE
• (0, 0)→(0, 3)→(0, 7)→(0, 1)→(4, 1)→(4, 4)→MIDDLE
• (8, 8)→(7, 8)→(4, 8)→(4, 4)→MIDDLE

解法のアプローチ

この問題は、バックトラッキング(深さ優先探索)を用いて解くのが効果的です。全体の手順は以下のとおりです。

• 迷路のサイズ N を 9 とします。
• 補助関数 is_ok() を定義します。引数として訪問済みセルの集合 visited と座標 pt を受け取り、pt の行・列がともに 0 以上 N 未満の範囲内であり、かつ pt が visited に含まれていない場合に true を返します。
• 移動方向を表す配列 dir_row = { -1, 1, 0, 0 } と dir_col = { 0, 0, -1, 1 } を用意します。これにより上・下・左・右の4方向を表現できます。
• スタート地点となる4つの隅の座標を row = { 0, 0, N-1, N-1 }、col = { 0, N-1, 0, N-1 } として定義します。
• 再帰関数 solve() を定義します。引数は迷路 maze、現在の経路 path、訪問済み集合 visited、現在位置 curr です。
  • curr が中央セル(N/2, N/2)と一致したら、経路を表示して処理を終了します。
  • そうでなければ、4方向それぞれについて次の処理を行います。
    • n := 現在のセルの値
    • x := curr.first + dir_row[i] * n
    • y := curr.second + dir_col[i] * n
    • next := 座標 (x, y) のペア
    • is_ok(visited, next) が true ならば、next を visited と path に追加し、solve() を再帰呼び出しします。戻ってきたら path と visited から next を削除して(バックトラック)、別の方向を試します。
• main 関数では、空の visited を用意し、4つの隅のセルを順にスタート地点として solve() を呼び出します。各呼び出しの後、path と visited からスタート地点を削除して次の隅へ進みます。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
#define N 9
bool is_ok(set<pair<int, int> > visited, pair<int, int> pt) {
    return (pt.first >= 0) && (pt.first < N) && (pt.second >= 0) && (pt.second < N) && (visited.find(pt) == visited.end());
}
void display_path(list<pair<int, int> > path) {
    for (auto it = path.begin(); it != path.end(); it++)
    cout << "(" << it->first << ", " << it->second << ")->";
    cout << "MIDDLE" << endl << endl;
}
int dir_row[] = {-1, 1, 0, 0};
int dir_col[] = { 0, 0, -1, 1};
int row[] = { 0, 0, N-1, N-1};
int col[] = { 0, N-1, 0, N-1};
void solve(int maze[N][N], list<pair<int, int> > &path, set<pair<int, int> > &visited, pair<int, int> &curr) {
    if (curr.first == N / 2 && curr.second == N / 2) {
        display_path(path);
        return;
    }
    for (int i = 0; i < 4; ++i) {
        int n = maze[curr.first][curr.second];
        int x = curr.first + dir_row[i]*n;
        int y = curr.second + dir_col[i]*n;
        pair<int, int> next = make_pair(x, y);
        if (is_ok(visited, next)) {
            visited.insert(next);
            path.push_back(next);
            solve(maze, path, visited, next);
            path.pop_back();
            visited.erase(next);
        }
    }
}
void search_path(int maze[N][N]) {
    list<pair<int, int> > path;
    set<pair<int, int> > visited;
    for (int i = 0; i < 4; ++i) {
        int x = row[i];
        int y = col[i];
        pair<int, int> pt = make_pair(x, y);
        visited.insert(pt);
        path.push_back(pt);
        solve(maze, path, visited, pt);
        path.pop_back();
        visited.erase(pt);
    }
}
int main() {
    int maze[N][N] = {
        {3, 4, 4, 4, 7, 3, 4, 6, 3},
        {6, 7, 5, 6, 6, 2, 6, 6, 2},
        {3, 3, 4, 3, 2, 5, 4, 7, 2},
        {6, 5, 5, 1, 2, 3, 6, 5, 6},
        {3, 3, 4, 3, 0, 1, 4, 3, 4},
        {3, 5, 4, 3, 2, 1, 3, 3, 5},
        {3, 5, 4, 3, 2, 6, 4, 4, 3},
        {3, 5, 1, 3, 7, 5, 3, 6, 3},
        {6, 2, 4, 3, 4, 5, 4, 5, 1}
    };
    search_path(maze);
}

入力

{{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}}

出力

(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(5, 1)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE
(0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(4, 4)->MIDDLE
(8, 8)->(7, 8)->(4, 8)->(4, 4)->MIDDLE

まとめ

このアルゴリズムの計算量は、各セルから最大4方向に分岐するため最悪情况下 O(4^(N×N)) となりますが、visited 集合によって同じセルの再訪問を防ぐことで、実際の探索範囲は大きく絞り込まれます。バックトラッキングの基本的なパターン(選択 → 再帰 → 選択の取り消し)を理解するのに適した題材ですので、ぜひ自分でも迷路のサイズや値を変えて試してみてください。