バックトラッキングで解く「迷路のネズミ」問題 ― C++プログラム実装ガイド

迷路のネズミ問題とは

「迷路のネズミ（Rat in a Maze）」は、バックトラッキング（探索の巻き戻し）を活用する有名なアルゴリズム問題の一つです。

迷路は2次元行列として表現され、一部のセルは通行止め（ブロック）されています。スタート地点となるセルと、ゴールとなるセルが存在し、ブロックされたセルに一切立ち入ることなく、スタートからゴールまでの経路を見つけることが課題です。以下は未解決状態の迷路の例です。

そしてこちらがその解答例です。

このパズルを解くには、まずスタートのセルから出発し、道が塞がれていない方向へ進みます。進んだ先でゴールに到達できればパズルは解けたことになります。到達できなければ、来た道を引き返し、別の方向へ進路を変更します。今回のコードでも、まさにこのロジックを実装していきます。

入力:
maze[][] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}}

出力:
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1

解法の考え方

まず、迷路を表す行列を作成します。行列の各要素は0または1で、1は通行不可のセル、0は移動可能なセルを表します。上記の迷路を行列で表すと次のようになります。

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

次に、同じサイズのもう一つの行列を作り、解答を保存します。ここでも要素は0または1で、1は経路上のセル、それ以外は0を表します。解答を表す行列は次の通りです。

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

準備が整ったら、スタートのセルからゴールのセルまでの経路を探します。手順は以下の通りです。

• 現在のセルがゴールかどうかを確認する。ゴールであればパズルは解けたことになる。

• ゴールでなければ、まず下方向への移動を試みる（移動先のセルは空いていること、かつすでに経路に含まれていないことが条件）。

• 移動できれば、そのまま下のセルへ進んで探索を続ける。

• 移動できなければ右方向を試す。右も塞がれているか通過済みであれば上方向へ。

• 同様に上にも進めない場合は左のセルへ移動する。

• 下・右・上・左の4方向すべてが不可能な場合は、一つ前のセルに戻り、経路を選び直す（バックトラッキング）。

まとめると、「現在のセルから他のセル（下・右・上・左）への移動を試み、どこにも移動できない場合は引き返して別の方向を選び直す」というシンプルな戦略です。

関数の役割

printsolution → 解答行列を画面に出力するだけの関数です。

solvemaze → バックトラッキングアルゴリズムを実装している本体の関数です。まず、現在のセルがゴールかどうかを if (r==SIZE-1) && (c==SIZE-1) で判定します。ゴールであればパズルはすでに解けています。そうでなければ、そのセルが有効な移動先かどうかを確認します。有効なセルであるための条件は次の3つです。

• インデックスが0以上SIZE-1以下の範囲内にあること（r>=0 && c>=0 && r<SIZE）
• 通行止めでないこと（maze[r][c] == 0）
• すでに経路に含まれていないこと（solution[r][c] == 0）

有効な移動であれば、そのセルを経路に加えて次のセルへ進みます。最初に下のセル solveMaze(r+1, c) を試し、解が得られなければ右、さらに上、左の順で試します。すべてのセルが失敗に終わった場合は solution[r][c] = 0 としてそのセルを経路から外し、別のセルへ戻ります。

サンプルコード

#include <iostream>
using namespace std;
#define SIZE 5
// 迷路問題
int maze[SIZE][SIZE] = {
   {0,1,0,1,1},
   {0,0,0,0,0},
   {1,0,1,0,1},
   {0,0,1,0,0},
   {1,0,0,1,0}
};
// 解答を保存する行列
int solution[SIZE][SIZE];
// 解答行列を出力する関数
void printsolution() {
   int i,j;
   for(i=0;i<SIZE;i++) {
      for(j=0;j<SIZE;j++) {
         printf("%d\t",solution[i][j]);
      }
      printf("\n\n");
   }
}
// バックトラッキングで迷路を解く関数
int solvemaze(int r, int c) {
   // ゴールに到達していれば迷路は解けた
   // ゴールは最後のセル(maze[SIZE-1][SIZE-1])
   if((r==SIZE-1) && (c==SIZE-1)) {
      solution[r][c] = 1;
      return 1;
   }
   // このセルに入れるかどうかの判定
   // インデックスは(0, SIZE-1)の範囲内であること
   // solution[r][c] == 0 は未訪問であることを保証
   // maze[r][c] == 0 は通行可能であることを保証
   if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0){
      // 安全であれば訪問する
      solution[r][c] = 1;
      // 下へ移動
      if(solvemaze(r+1, c))
         return 1;
      // 右へ移動
      if(solvemaze(r, c+1))
         return 1;
      // 上へ移動
      if(solvemaze(r-1, c))
         return 1;
      // 左へ移動
      if(solvemaze(r, c-1))
         return 1;
      // バックトラッキング
      solution[r][c] = 0;
      return 0;
   }
   return 0;
}
int main() {
   // 解答行列の全要素を0で初期化
   int i,j;
   for(i=0; i<SIZE; i++) {
      for(j=0; j<SIZE; j++) {
         solution[i][j] = 0;
      }
   }
   if (solvemaze(0,0))
      printsolution();
   else
      printf("No solution\n");
   return 0;
}