バックトラックで文字の盤の上をたどって言葉が作れるか調べる

英字が升目に並んだ盤の上で、隣り合うマスをたどって言葉を作れるかを調べます。通ったマスに印を付けて進み、行き止まりなら印を外して戻る練習です。

海外で定番の問題リスト 4 本には入っていません

問題

言葉探しのパズルの盤を、英大文字の行の並び grid で受け取ります。grid[r] は r 行目の文字列で、その c 字目が r 行 c 列のマスの字です。言葉 word を、盤の上で次の決まりでたどって作れるなら true、作れなければ false を返す関数を書いてください。

どのマスから始めてもかまいません
次の字へは、上下左右のどれかで隣り合うマスへ進みます。斜めには進めません
1 つの言葉の中で、同じマスを 2 回使うことはできません
行の数と列の数はどちらも 1 以上 6 以下で、どの行も同じ長さです。word の長さは 1 以上 15 以下で、英大文字だけです

入力と出力の例

例 1

左上の C から下の O、右の D、右の E とたどると CODE になります。

grid = ["CAT", "ODE", "XRS"] word = "CODE"

true

例 2

CODE までは作れますが、最後の D は E の隣に 1 つしかなく、そのマスはもう使っています。同じマスは 2 回使えません。

grid = ["CAT", "ODE", "XRS"] word = "CODED"

false

例 3

右上の T から左の A までは進めますが、A の隣は C と D で、E がありません。ほかに T は無いので、TAE はたどれません。

grid = ["CAT", "ODE", "XRS"] word = "TAE"

false

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「文字の 2 次元の盤と単語があります。隣り合うマスをたどって単語を作れるか返してください」
書き終えると「同じマスを使わないように、どう印を付けましたか？戻るときに何をしますか？」と聞かれます
「単語がたくさんあったら？」と、トライ木と組み合わせる版へ広げて聞かれることがあります

斜めに進めるか、同じマスを使い回せるかを最初に確かめておくと、たどり方が決まります。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。

再帰は、同じ形の小さい問題に分けて自分を呼ぶ書き方です。木の深さや、全部の組み合わせを数える問題で使います。

まず考える手順

段 1

言葉の 1 字目と同じ字のマスが、始めの候補です。全部のマスを始めとして試し、どれか 1 つで作れれば true です。

段 2

あるマスから「言葉の k 字目以降を作れるか」を、自分を呼ぶ関数 (再帰) で調べます。マスが盤の外、もう使ったマス、k 字目と違う字のどれかなら作れません。k 字目と同じなら、上下左右の 4 つのマスから k + 1 字目以降を調べます。言葉の最後まで合えば作れます。

段 3

同じマスを 2 回使わないように、進むときにそのマスへ印を付けます。4 方向を調べ終えて戻るときに、印を外します。外さないと、別の道で同じマスを通れなくなり、作れる言葉を見落とします。この「印を付けて進み、外して戻る」がバックトラックです。

段 4

どこかの道で言葉ができたら、残りの方向や残りのマスは調べずにすぐ true を返します。Python の or と JavaScript の || は、左が真なら右を呼ばないので、そのまま早く抜けられます。

解答

Python

def word_search(grid, word):
    h = len(grid)
    w = len(grid[0])
    used = set()

    def dfs(r, c, k):
        if k == len(word):
            return True
        if not (0 <= r < h and
                0 <= c < w):
            return False
        if (r, c) in used:
            return False
        ch = grid[r][c]
        if ch != word[k]:
            return False
        used.add((r, c))
        k += 1
        found = (
            dfs(r + 1, c, k) or
            dfs(r - 1, c, k) or
            dfs(r, c + 1, k) or
            dfs(r, c - 1, k))
        used.remove((r, c))
        return found

    for r in range(h):
        for c in range(w):
            if dfs(r, c, 0):
                return True
    return False

JavaScript

function wordSearch(
  grid, word
) {
  const h = grid.length;
  const w = grid[0].length;
  const used = grid.map(
    () => Array(w).fill(false));
  const dfs = (r, c, k) => {
    if (k === word.length) {
      return true;
    }
    if (r < 0 || r >= h ||
      c < 0 || c >= w) {
      return false;
    }
    if (used[r][c] ||
      grid[r][c] !== word[k]) {
      return false;
    }
    used[r][c] = true;
    k++;
    const found =
      dfs(r + 1, c, k) ||
      dfs(r - 1, c, k) ||
      dfs(r, c + 1, k) ||
      dfs(r, c - 1, k);
    used[r][c] = false;
    return found;
  };
  return grid.some((row, r) =>
    [...row].some((_, c) =>
      dfs(r, c, 0)));
}

Go

func wordSearch(
	grid []string, word string,
) bool {
	h := len(grid)
	w := len(grid[0])
	used := make([][]bool, h)
	for r := range used {
		used[r] = make([]bool, w)
	}
	var dfs func(r, c, k int) bool
	dfs = func(r, c, k int) bool {
		if k == len(word) {
			return true
		}
		if r < 0 || r >= h ||
			c < 0 || c >= w {
			return false
		}
		if used[r][c] ||
			grid[r][c] != word[k] {
			return false
		}
		used[r][c] = true
		k++
		found := dfs(r+1, c, k) ||
			dfs(r-1, c, k) ||
			dfs(r, c+1, k) ||
			dfs(r, c-1, k)
		used[r][c] = false
		return found
	}
	for r := 0; r < h; r++ {
		for c := 0; c < w; c++ {
			if dfs(r, c, 0) {
				return true
			}
		}
	}
	return false
}

印は盤とは別の入れ物 (Python は集合、JavaScript と Go は真偽の 2 次元の並び) に付けています。盤の字を # などに書き換えて印にする書き方もありますが、受け取った盤を書き換えずに済みます。

計算量

時間は O(m × n × 3^L) です。m と n は盤の行と列の数、L は言葉の長さです。始めのマスが m × n 個あり、1 歩目のあとは来た方へ戻れないので、進める向きは 3 つまでです
使う記憶は O(m × n + L) です。印の入れ物が盤と同じ大きさで、再帰の深さが L までです

よくある間違い

戻るときに印を外さない。 1 つの道で使ったマスが、別の道でも使えなくなります。始めのマスを変えたときにも印が残り、作れる言葉を false にしてしまいます
盤の外かどうかより先にマスの字を見る。範囲の外を読むと、Python は負の番号で反対の端を読み、JavaScript は undefined、Go は止まります。範囲を先に確かめます
言葉の最後まで合ったかを、字を比べたあとで確かめる。 k が言葉の長さに達したら、その時点で true です。順を逆にすると、言葉の最後の字のマスが盤の端にあるときに外を読みに行きます
斜めにも進む。決まりにない向きへ進むと、作れないはずの言葉を true にします

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def word_search(grid: list[str], word: str) -> bool:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(word_search(["CAT", "ODE", "XRS"], "CODE"))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します