JavaScriptのバックトラッキングパターンで解くアルゴリズム問題：全マスを通るユニークパスの総数

今回は、バックトラッキング（Backtracking）パターンを使って解く典型的なアルゴリズム問題を、JavaScriptで実装してみましょう。

2次元グリッド上には、次の4種類のマスが存在します。

• 1：スタート地点のマス（必ず1つだけ存在する）
• 2：ゴール地点のマス（必ず1つだけ存在する）
• 0：自由に移動できる空きマス
• -1：障害物（通行できないマス）

実装する関数は、スタートからゴールまで「上下左右の4方向移動」だけで進み、かつ障害物以外のすべてのマスをちょうど1回ずつ通過する経路の総数を返すものです。

例

const arr = [
    [1,0,0,0],
    [0,0,0,0],
    [0,0,2,-1]
];
const uniquePaths = (arr, count = 0) => {
    const dy = [1,-1,0,0], dx = [0,0,1,-1];
    const m = arr.length, n = arr[0].length;
    const totalZeroes = arr.map(row => row.filter(num => num === 0).length)
                           .reduce((sum, next) => sum + next, 0);
    const depthFirstSearch = (i, j, covered) => {
        if (arr[i][j] === 2){
            if (covered === totalZeroes + 1) count++;
            return;
        }
        for (let k = 0; k < 4; k++)
            if (i+dy[k] >= 0 && i+dy[k] < m && j+dx[k] >= 0 && j+dx[k] < n
                && arr[i+dy[k]][j+dx[k]] !== -1){
                arr[i][j] = -1;
                depthFirstSearch(i+dy[k], j+dx[k], covered+1);
                arr[i][j] = 0;
            }
        return;
    };
    for (let row = 0; row < m; row++)
        for (let col = 0; col < n; col++)
            if (arr[row][col] === 1){
                arr[row][col] = -1;
                depthFirstSearch(row, col, 0);
                break;
            }
    return count;
};
console.log(uniquePaths(arr));

コードの解説

1. 事前準備：移動方向を表す配列 dy・dx を用意して、上下左右への反復処理をシンプルにします。あわせてグリッド内の空きマス（0）の総数を数えておき、再帰のベースケースに達したときに「すべてのマスを訪れたかどうか」を判定できるようにしています。
2. DFSとバックトラッキング：depthFirstSearch の中では、現在のマスを -1 でマークして「この経路ですでに通過済み」であることを示します。4方向それぞれについて、グリッドの範囲内かつ障害物でなければ再帰的に探索を進め、呼び出しから戻ったらマークを 0 に復元します。この「マーク → 探索 → 復元」の一連の流れこそがバックトラッキングの核心です。ゴール（2）に到達した時点で、訪問カウンター covered が totalZeroes + 1 と一致していれば、全マスを漏れなく通った完全な経路としてカウントします。
3. 探索の開始：最後にスタートマスを探して -1 に設定し、そこから DFS を起動します。条件を満たすすべての経路を数え上げ、その合計を返り値として返します。

出力

コンソールには次のように表示されます。

2

補足：なぜバックトラッキングが適しているのか

この問題は「すべてのマスをちょうど1回ずつ訪れる」という強い制約があるため、単純な動的計画法では解けません。各ステップで4方向に分岐しながら行き止まりまで掘り下げ、失敗すれば直前の状態へ巻き戻して別の道を試す——バックトラッキングは、こうした全経路の列挙に最も適した手法です。最悪の時間計算量は O(4^(m×n)) ですが、障害物や訪問済みマスによる枝刈りの効果で、実際の探索範囲は大きく絞り込まれます。