JavaScriptでボグル（Boggle）盤上の単語を検証するアルゴリズム

問題概要

ボグル（Boggle）盤とは、個々の文字が並んだ2次元配列のことです。例えば以下のようなものがあります。

const board = [
    ["I","L","A","W"],
    ["B","N","G","E"],
    ["I","U","A","O"],
    ["A","S","R","L"]
];

ここで求められているのは、JavaScriptの関数を作成し、ボグル盤と文字列を受け取って、その文字列がボグル盤上の有効な解答（バリッドな推測）であるかどうかを判定することです。

有効な推>有効な推測とは、隣接するセル（上下左右および斜め方向）をつなぎ合わせて形成できる文字列であり、かつ一度使用したセルを再利用しないという条件を満たすものを指します。

例えば、上記の盤面では「LINGO」や「ILNBIA」は有効な推測ですが、「BUNGIE」や「SINUS」は無効となります。

実装例

以下が実際のコードです。

const board = [
    ["I","L","A","W"],
    ["B","N","G","E"],
    ["I","U","A","O"],
    ["A","S","R","L"]
];
const guess = 'BINGO';
const checkWord = (board = [], guess = '') => {
    const numRows = board.length;
    const numCols = board[0].length;
    let queue = board.reduce((acc, row, i) => {
        row.forEach((x, j) => {
            if (x === guess[0]) {
                acc.push ( { pos: {r: i, c: j} , nextIndex: 1, path: [numCols*i + j ] } );
            }
        });
        return acc;
    }, []);
    let exploreWord = (obj, queue) => {
        let allMoves = [ {r: obj.pos.r - 1, c: obj.pos.c },
        {r: obj.pos.r + 1, c: obj.pos.c },
        {r: obj.pos.r, c: obj.pos.c - 1 },
        {r: obj.pos.r, c: obj.pos.c + 1 },
        {r: obj.pos.r - 1, c: obj.pos.c - 1 },
        {r: obj.pos.r - 1, c: obj.pos.c + 1 },
        {r: obj.pos.r + 1, c: obj.pos.c - 1 },
        {r: obj.pos.r + 1, c: obj.pos.c + 1 }];
        allMoves.forEach((o) => {
            let index = numCols * o.r + o.c;
            if (o.r >= 0 && o.r < numRows && o.c >= 0 && o.c < numCols) {
                if (board[o.r][o.c] === guess[obj.nextIndex] && !obj.path.includes(index)) {
                    let cloneObj = JSON.parse(JSON.stringify(obj));
                    cloneObj.pos = { r: o.r, c: o.c };
                    cloneObj.nextIndex += 1;
                    cloneObj.path.push(index);
                    queue.push(cloneObj);
                }
            }
        });
    };
    while (queue.length > 0) {
        let obj = queue.shift();
        if (obj.nextIndex === guess.length) {
            return true;
        }
        exploreWord(obj, queue);
    }
    return false;
};
console.log(checkWord(board, guess));

コードの解説

このコードでは、以下の手順で処理を行っています。

• まず2次元配列全体を走査し、探索したい単語の最初の文字と一致するセルをすべて見つけます。

• 一致したセルの「位置」と「次に照合すべき文字のインデックス」をキューに追加します。キューが空になるまで、先頭のオブジェクトを取り出しては処理を続けます。

• 取り出したセルから8方向（上下左右＋斜め）すべてを調べます。隣接セルの文字が単語の次の文字と一致し、かつそのセルがまだ使用されていない場合は、位置情報とインデックスを更新したうえでキューに追加します。条件を満たさない場合はそのオブジェクトを破棄します。

• この処理を、単語全体がマッチするまで、あるいはマッチ候補がなくなるまで繰り返します。最終的に完全なマッチが見つかればtrueを、見つからなければfalseを返します。

この手法は幅優先探索（BFS）の一種であり、各探索経路を独立に管理することで「セルの再利用禁止」ルールを正確に守れる点がポイントです。

出力結果

true