Pythonで2次元グリッド内の単語検索を実装する方法【再帰・バックトラッキング】

2次元のボード（グリッド）と1つの単語が与えられたとき、その単語がグリッド内に存在するかどうかを判定する問題を考えてみましょう。単語は、順番に隣接するセルの文字をつなげて構成されます。ここでいう「隣接」とは、上下左右に位置するセルのことです。また、同じセル（同じ文字）を複数回使用することはできません。

例として、次のようなマトリックスがあるとします。

このとき、単語「ABCCED」が与えられれば答えは True、「SEE」も True になります。しかし「ABCB」の場合は、同じセルを再利用できないため False となります。

解法のアプローチ：再帰とバックトラッキング

この問題は再帰的な探索（バックトラッキング）を使うことで効率的に解けます。各セルから出発して上下左右へ文字をたどり、条件に合わなくなったら一歩戻って別の経路を試すイメージです。

手順の詳細

• 再帰メソッド find() を定義します。引数はマトリックス mat、単語 word、行 row、列 col、インデックス i です。最初は i = 0 から始めます。
• i が単語の長さと等しくなれば、すべての文字を照合できたということなので True を返します。
• row が行数以上または0未満、col が列数以上または0未満、もしくは word[i] が mat[row][col] と一致しない場合は False を返します。
• mat[row][col] := "*" として、現在のセルを一時的に「訪問済み」マークを付けます。これにより同じセルを二重に使うことを防ぎます。
• 4方向（下・上・右・左）それぞれに対して find() を再帰的に呼び出し、結果を OR で結合します。
  res := find(mat, word, row+1, col, i+1) or find(mat, word, row-1, col, i+1) or find(mat, word, row, col+1, i+1) or find(mat, word, row, col-1, i+1)
• mat[row][col] := word[i] としてセルの値を元に戻します（これがバックトラッキングの核心部分です）。
• res を返します。

メイン処理の流れ

• n := 行数、m := 列数 とします。
• すべてのセル (i, j) についてループを行い、word[0] が mat[i][j] と一致するセルを見つけたら、そこを出発点として find() を呼び出します。
• find() の結果が False でなければ、単語が見つかったので True を返します。

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution(object):
   def exist(self, board, word):
      n = len(board)
      m = len(board[0])
      # すべてのセルを出発点候補として調べる
      for i in range(n):
         for j in range(m):
            if word[0] == board[i][j]:
               if self.find(board, word, i, j):
                  return True
      return False
   def find(self, board, word, row, col, i=0):
      # 単語の最後まで照合できたら成功
      if i == len(word):
         return True
      # 範囲外または文字が一致しない場合は失敗
      if row >= len(board) or row < 0 or col >= len(board[0]) or col < 0 or word[i] != board[row][col]:
         return False
      # 訪問済みマークを付けて同じセルの再利用を防止
      board[row][col] = '*'
      # 4方向へ再帰的に探索
      res = self.find(board, word, row+1, col, i+1) or self.find(board, word, row-1, col, i+1) or self.find(board, word, row, col+1, i+1) or self.find(board, word, row, col-1, i+1)
      # セルの値を元に戻す（バックトラッキング）
      board[row][col] = word[i]
      return res
ob1 = Solution()
print(ob1.exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "SEE"))

入力

[["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
"SEE"

出力

True

まとめ

この実装では、グリッド上の各セルを起点として深さ優先探索（DFS）を行い、訪問済みセルを一時的に書き換えることで同じ文字の再利用を防いでいます。探索後には必ず元の値に戻すことで、他の出発点からの探索にも影響を与えません。計算量は最悪ケースで O(m × n × 3^L)（L は単語の長さ）となり、バックトラッキングを用いた典型的なグリッド探索問題として、LeetCode の「Word Search」などでもおなじみのパターンです。