クロスワード盤面をブラウザで動的生成する打ち切り付き探索

パズルゲームで「毎回ちがう盤面を出す」と決めた瞬間に、盤面を作るコードが要る。クロスワードのような交差する語の盤面は、真面目に作ろうとすると制約充足問題（CSP）になり、バックトラッキング付きのソルバを書くことになる。

ただし、ブラウザで遊ぶゲームの盤面生成に必要なのは「最適な盤面」ではない。「成立する盤面が1枚あればよい」である。この条件なら、探索を解かずに「ランダムに作ってから成立しているか確かめる」で十分に間に合う。

この記事では、hashito.biz のポケモンクロスワードが使っている生成器（public/tools/pokecross/generator.js）の実装を追いながら、生成 & 検査（generate-and-test）方式を実用に耐えさせるために何が要るかを整理する。要点は3つで、打ち切り予算・座標の後から正規化・盤面の「引き直し」である。最後に、この生成器を Node からそのまま呼んで盤面を出すスクリプトを置く。

前提: 生成器は DOM に触らない

このファイルは UMD でも ES モジュールでもなく、素の IIFE で window.PokeGen に関数を生やすだけの層である。冒頭のコメントにも「DOM非依存」と書かれている。

window.PokeGen = {
  make: make, makeChallengeSet: makeChallengeSet, rampLength: CHALLENGE_RAMP.length,
  makeEndless: makeEndless, endlessPlan: endlessPlan, blankGivens: blankGivens,
  endlessStyleCount: endlessStyleCount,
  ENDLESS_BANDS: ENDLESS_BANDS, ENDLESS_BLANKS: ENDLESS_BLANKS
};

DOM を触らないので、global.window = {} を用意すれば Node から require できる。盤面生成のように「目で見ても正しさが分からない」処理は、描画から切り離しておかないと検証手段が消える。実際このリポジトリには test/pokecross-generator.test.js があり、node --test で18件のテストが動く。

盤面の出力形式は次のとおりで、n の値が意味を持つ。

• n === -2 … 最初から見えているマス（ヒント）
• n === -1 … 交差の空欄（入力するが答えではない）
• n >= 0 … 答えのマス。値は答えの何文字目か

1. 「作って確かめる」の骨組み

生成の中心は crossword() である。やっていることは単純だ。

1. 語のリストをシャッフルする
2. 先頭から、答えにしたい長さ [minL, maxL] に収まる語を1つ選ぶ（これが答え）
3. 答えの各文字について、その文字を含む語をリストから1本ずつ拾う
4. 答えの文字数ぶん拾えたら成功。足りなければシャッフルからやり直す

var p = shuffle(POKE);
var ai = -1;
for (var k = 0; k < p.length; k++) { if (p[k].length >= minL && p[k].length <= maxL) { ai = k; break; } }
if (ai < 0) continue;
var anser = p.splice(ai, 1)[0];

ここには枝刈りも順序付けもない。 失敗したら全部捨てて引き直す。CSP ソルバなら「この語を置くと以降が詰む」を検出して部分的に戻すが、この生成器はそれをやらない。語彙が数十〜数千語あって、答えが3〜6文字しかないなら、成功率が十分高いので引き直したほうが速くて短い。

2. 打ち切り予算がないと止まらない

生成 & 検査方式の弱点は明快で、成立しない要求を渡されると永久に回り続けることである。「9文字の答え」を要求されても、語彙に9文字の語が無ければ何度シャッフルしても見つからない。ブラウザのメインスレッドでこれをやると、タブが固まる。

このファイルはそこに2段の防御を入れている。1段目は、シャッフルする前の存在チェックである。

function hasAnswerCandidate(POKE, minL, maxL) {
  for (var i = 0; i < POKE.length; i++) {
    if (POKE[i].length >= minL && POKE[i].length <= maxL) return true;
  }
  return false;
}

O(n) を1回走らせるだけで、make(9, 10) のような「そもそも候補が無い」要求は即座に null を返す。minL > maxL のような壊れた引数もここで落ちる。

2段目は、シャッフル回数そのものの上限である。ソースのコメントに実測値が残っている。

/* 生成の総試行回数（shuffle 回数）の上限。
 * 実測（各レベル 20,000 回生成・全成功）での最悪 shuffle 回数は
 *   [3,3]=16 / [4,4]=35 / [5,5]=96 / [5,6]=51
 * 最も重い [5,5] の 96 に対して 30 倍以上の余裕を取り 3000 とする。 */
var MAX_SHUFFLES = 3000;

この決め方が実務的に大事なところである。 上限を「勘で大きめ」にすると、実際に詰んだときの待ち時間が読めない。ここでは (a) 正常系の最悪値を実測し、(b) その30倍を上限にし、(c) 1回あたりのコスト（約0.35ms）から打ち切り時の所要時間（1秒前後）を出している。上限値そのものより、上限に達したときに何秒で戻るかを見積もっているかどうかが、UI を固めないための分かれ目になる。

予算は budget オブジェクトで持ち回り、make() の外側ループと crossword() の内側ループで共有する。片方だけに上限を置くと、外側が回り続けてしまう。

var budget = { left: MAX_SHUFFLES };
for (var t = 0; t < 4000 && budget.left > 0; t++) { ... }

3. 座標は原点を気にせず置いて、後から正規化する

盤面を組み立てる build() は、最初の語をこの位置から置き始める。

var vmap = {}, vtype = 0, point = [100, 100];

[100, 100] は画面上の意味を持たない。語をどちらへ伸ばしても座標が負にならないための「十分な余白」である。交差する語は上にも左にも伸びるので、[0, 0] から始めると負のインデックスが出る。

マス目は二次元配列ではなく "x,y" を鍵にした辞書で持つ。

function s2p(v) { return v.split(",").map(Number); }
function p2s(v) { return v.join(","); }

配列だと事前に大きさを決める必要があるが、辞書なら決めなくていい。そして全部置き終わったあとに、実際に使ったマスの最小・最大を取って原点へ寄せる。

var minx = Infinity, miny = Infinity, maxx = -Infinity, maxy = -Infinity, k;
for (k in vmap) { var pp = s2p(k); minx = Math.min(minx, pp[0]); ... }
for (k in vmap) { var q = s2p(k), v = vmap[k]; cells.push({ x: q[0] - minx, y: q[1] - miny, ... }); }

盤面の幅と高さもここで初めて決まる（maxx - minx + 1）。先に盤面サイズを決めて、その中に収まるように語を置く設計にすると「収まらないからやり直し」が増えるが、この順序なら置いた結果がそのまま盤面になる。生成 & 検査方式と相性がよい。

4. 「型に沿って伏せる」で難易度を変える

このゲームには10問で終わるチャレンジと、終わりのないエンドレスがある。エンドレスで難しくする方法として、ソースは答えの文字数を伸ばし続けることを意図的に避けている。コメントがその理由を書いている。要約すると、3→4→5→6 と伸ばしても「同じ作業が長くなるだけ」で、思い出し方が変わらないからである。

かわりに変えるのは、盤面のどこが見えているかのほうだ。交差する語のマス（n === -2）を、型に沿って空欄（n === -1）に落とす。

var ENDLESS_BLANKS = ["none", "tail", "head", "alt", "most"];

• tail … 各語の末尾を伏せる（頭から読んで最後を補う）
• head … 各語の先頭を伏せる（尻から逆に辿る）
• alt … 市松に伏せる
• most … 答えマスの隣以外をほぼ伏せる

判定は隣接マスの有無だけで書かれている。語が横並びか縦並びかを別に保存していないのがうまいところで、隣にマスがあるかどうかから復元している。

var horiz = has(c.x - 1, c.y) || has(c.x + 1, c.y);
var vert  = has(c.x, c.y - 1) || has(c.x, c.y + 1);

そして重要なのは、答えマス（n >= 0）には絶対に触らないことである。伏せる操作は n === -2 のマスだけを -1 に変える。正解判定は「すべての入力マスが正解文字と一致するか」なので、マスの種類を変えるだけで出題内容が変わる。判定側に手を入れていない。

出題方針は乱数を使わず、問題番号から決まる。

function endlessPlan(n) {
  n = Math.max(0, n | 0);
  var band = ENDLESS_BANDS[n % ENDLESS_BANDS.length];
  var blank = ENDLESS_BLANKS[Math.floor(n / 2) % endlessStyleCount(n)];
  return { minL: band[0], maxL: band[1], blank: blank, label: ENDLESS_BLANK_LABEL[blank] };
}

文字数の帯は毎問ずれ、伏せ方の型は2問ごとにずれる。同じ番号なら必ず同じ方針になるので、テストが書けるし、順番を再現して不具合を追える。

伏せられない盤面が出る

型を選んでも1マスも伏せられない盤面がある。たとえば tail は「語の終わりのマス」を伏せる型なので、語の終わりがすべて答えマスだった盤面では何も起きない。画面には「語尾かくし」と型の名前が出るので、素の盤面のままその名前を出すと説明と中身が食い違う。

そこで makeEndless() は、伏せられる盤面が出るまで最大12回引き直す。

for (var i = 0; i < 12; i++) {
  var pz = make(plan.minL, plan.maxL) || make(3, 4);
  if (!pz) continue;
  out = blankGivens(pz, plan.blank);
  if (plan.blank === "none" || (out.blanked || 0) > 0) break;
}

この率は語彙に依存する。 ソースのコメントには実際の語彙で tail が 6.1%（3000枚中183枚）と記録されているが、後述のスクリプトで技術用語50語の語彙に差し替えて1000枚ずつ測ると tail が 17.9% になった。語が短く末尾の重なりが起きやすいほど上がる。自分の語彙に入れ替えるなら、この率は測り直す必要がある（12回の引き直しで足りるかがここで決まる）。

実際に試す

Node.js 20 以降があれば依存は要らない。リポジトリを持っていなくても、公開されている生成器を1本だけ取ってくれば動く。

mkdir -p /tmp/xw && cd /tmp/xw
curl -sO https://hashito.biz/tools/pokecross/generator.js

同じディレクトリに demo.js を置く。語彙は何でもよいので、ここでは技術用語のカタカナ語に差し替える（生成器は window.POKE_NAMES からカタカナの語だけを読む）。

// 生成器は DOM に触らないので、window を用意すれば Node から読める
global.window = {};
window.POKE_NAMES = [
  "コンパイラ", "インタプリタ", "メモリ", "キャッシュ", "カーネル", "プロセス", "スレッド",
  "バッファ", "ポインタ", "レジスタ", "ネットワーク", "パケット", "ルータ", "サーバ",
  "クライアント", "ソケット", "プロトコル", "トークン", "セッション", "データベース",
  "インデックス", "テーブル", "カラム", "トランザクション", "クエリ", "スキーマ",
  "コンテナ", "イメージ", "クラスタ", "デプロイ", "ブラウザ", "キャンバス", "スタイル",
  "スクリプト", "モジュール", "バンドル", "ライブラリ", "テンプレート", "アルゴリズム",
  "キュー", "スタック", "ハッシュ", "ベクトル", "パラメータ", "メトリクス", "トレース",
  "アラート", "モニタ", "リトライ", "タイムアウト"
];
require("./generator.js");
const G = window.PokeGen;

function render(pz) {
  const g = Array.from({ length: pz.h }, () => Array(pz.w).fill("・"));
  for (const c of pz.cells) g[c.y][c.x] = c.n === -2 ? c.c : c.n >= 0 ? "■" : "□";
  return g.map((r) => r.join("")).join("\n");
}

const pz = G.make(4, 5);
console.log("答え:", pz.answer, " 盤面:", pz.w + "x" + pz.h, " 入力マス:", pz.inputs);
console.log(render(pz));
console.log("■=答えのマス / □=交差の空欄 / ・=マス無し");

let ok = 0;
const t0 = Date.now();
for (let i = 0; i < 2000; i++) if (G.make(5, 5)) ok++;
console.log("\n答え5文字の盤面を 2000 回:", ok, "成功 /", Date.now() - t0, "ms");
console.log("成立しない要求 make(9,10):", G.make(9, 10));

for (let n = 0; n < 10; n++) console.log("エンドレス " + n + " 問目:", G.endlessPlan(n));

実行する。

node demo.js

盤面は毎回変わる（生成器は Math.random を使う）ので、出力の形だけ見てほしい。2000回の所要時間も環境で変わり、手元の Node.js 20.17.0 では 3.9〜4.1 秒（1枚あたり約 2ms）だった。

答え: ベクトル  盤面: 7x10  入力マス: 5
・・・・デ・・
・・・・ー・・
・・・・タ・・
・・・・■・・
・・・・ー・・
メトリ■□・・
・・・・ク・・
・・・・リ・・
・・・・プ・・
・・プロ■コ■
■=答えのマス / □=交差の空欄 / ・=マス無し

答え5文字の盤面を 2000 回: 2000 成功 / 3896 ms
成立しない要求 make(9,10): null
エンドレス 0 問目: { minL: 3, maxL: 3, blank: 'none', label: 'そのまま' }
エンドレス 1 問目: { minL: 4, maxL: 4, blank: 'none', label: 'そのまま' }
...
エンドレス 6 問目: { minL: 3, maxL: 3, blank: 'tail', label: '語尾かくし' }

この盤面を読み解くと、生成器がやっていることが見える。5列目を縦に読むと、上から6マスが データ■ー□、6行目から下の5マスが □クリプ■ になっている。この2語は6行目のマスを共有していて、データベース の「ス」と スクリプト の「ス」が同じ1マスである。答えの ベクトル は4マスに散っていて、ベ（4行目・5列目）・ク（6行目の メトリ■）・ト（10行目・5列目）・ル（10行目の プロ■コ■ の末尾）に対応する。

make(9, 10) が null を返しているのが、hasAnswerCandidate が効いている証拠である。この行だけコメントアウトして走らせると、体感できるほど待たされてから null が返る（打ち切り予算のおかげで、固まりはせず戻ってはくる）。

伏せ方の型ごとの「1マスも伏せられない率」も測れる。上のファイルの末尾に足す。

for (const style of G.ENDLESS_BLANKS) {
  let zero = 0, n = 0;
  for (let i = 0; i < 1000; i++) {
    const p = G.make(4, 5);
    if (!p) continue;
    n++;
    const o = G.blankGivens(p, style);
    if (style !== "none" && (o.blanked || 0) === 0) zero++;
  }
  console.log(style, (zero / n * 100).toFixed(1) + "%", "(" + zero + "/" + n + ")");
}

上の50語の語彙での結果はこうなった。

none 0.0% (0/1000)
tail 17.9% (179/1000)
head 0.0% (0/1000)
alt 0.0% (0/1000)
most 0.0% (0/1000)

tail だけが突出する。語の末尾は答えマスに使われやすいためで、語彙を差し替えたときに最初に確認すべき数字はここである。

まとめ

• 「成立する盤面が1枚あればよい」なら、CSP ソルバではなく生成 & 検査で十分に間に合う。枝刈りを書かないぶん実装が短い
• 生成 & 検査で必須なのは打ち切り予算。上限値は勘で決めず、正常系の最悪試行回数を実測し、その倍数を取り、打ち切り時に何秒で戻るかまで見積もる
• 候補の存在チェック（O(n) 1回）を先に置くと、成立しない要求を総当たり前に落とせる
• 座標は余白を取った位置から置き、最後に最小値を引いて正規化する。盤面サイズを先に決めない
• 難易度は「量を増やす」より「見えている情報を型に沿って削る」ほうが、問われ方そのものを変えられる。ただし型が空振りする盤面の率は語彙に依存するので測る

生成器の実物は ポケモンクロスワード で動いている。ほかのゲームは hashito.biz のゲーム一覧にある。本記事の出力例は Node.js 20.17.0 で実際に実行した結果である。