必ず解けるパズルを自動生成する — 麻雀ソリティアの逆生成アルゴリズム実装記

パズルゲームを自作するとき、最初にぶつかる技術的な壁が「生成した問題が必ず解けることをどう保証するか」です。私は最近、積み上がった牌からフリーな牌をタップ2回で消していく麻雀ソリティア (積み牌を崩すマッチングパズル) を個人開発しました。牌をランダムに配置するだけだと、どうやっても最後まで消せない「詰み盤」が一定確率で生まれます。これはパズルゲームとして致命的で、プレイヤーは「自分が下手なのか、そもそも解けないのか」が分からないまま理不尽に負けます。この記事では、私がこの問題を「逆生成 (リバース生成)」という構成的なアプローチで解決した実装を、実際のコード込みで共有します。考え方自体は数独・ナンプレ・倉庫番など多くの生成型パズルに応用が効きます。

なぜランダム配置は詰むのか — フリー牌の定義

このパズルでは、牌は3次元的に積まれます。座標は x, y がハーフ単位 (牌は2×2マスを占有)、z がレイヤー (段) です。ある牌が「今すぐ取れる=フリー」かどうかは、2つの条件で決まります。第一に上に牌が乗っていないこと。第二に左右どちらかが開いていること。コードにするとこうなります。

function isFree(tile, tiles) {
  let leftBlocked = false, rightBlocked = false;
  for (const t of tiles) {
    if (t === tile || !t.alive) continue;
    // 上の段に重なっている牌があれば取れない
    if (t.z === tile.z + 1 && overlapsXY(t, tile)) return false;
    // 同じ段で左右に密着している牌を記録
    if (t.z === tile.z && Math.abs(t.y - tile.y) < 2) {
      if (t.x === tile.x - 2) leftBlocked = true;
      else if (t.x === tile.x + 2) rightBlocked = true;
    }
  }
  return !(leftBlocked && rightBlocked); // 両側塞がれていなければフリー
}

問題は、絵柄をランダムに割り当てると、「同じ絵柄の2枚が、両方フリーになる瞬間が二度と来ない配置」が発生しうることです。たとえば同じ絵柄の牌が縦に積み重なっていると、下の牌は上の牌を消さないと取れず、しかし上の牌の相方は別の場所にあって先に消えてしまう…といった依存の輪が生まれ、盤が途中で完全に固まります。ランダム生成してから「これは解けるか?」を総当たりで判定する方法もありますが、盤が大きいと探索コストが爆発し、しかも失敗したら作り直しで、いつ成功するか読めません。

逆生成: 「解ける並び」を先に作ってしまう

発想を逆にします。完成 (=全部消えた) 状態から巻き戻すのです。空の盤に牌を「置いていく」のではなく、満杯の盤から、フリーなペアを2枚ずつ取り除いていくシミュレーションを最後まで走らせます。取り除いた順序を記録しておけば、その逆順こそが「この盤を必ず解ける手順」になります。これは解の存在を探索で確かめるのではなく、解の手順を構成的に作りながら盤を組むので、生成が終わった時点で解の存在が証明済みという性質を持ちます。

function deal(layout, kindCount, rng, maxAttempts = 60) {
  for (let attempt = 1; attempt <= maxAttempts; attempt++) {
    const tiles = layout.tiles.map((p, i) =>
      ({ x: p.x, y: p.y, z: p.z, alive: true, kind: -1, i }));
    const order = [];
    let remaining = tiles.length, ok = true;

    // 満杯の盤から「フリーな2枚」をランダムに取り続ける
    while (remaining > 0) {
      const free = freeTiles(tiles);      // 今フリーな牌
      if (free.length < 2) { ok = false; break; } // 詰んだらこの試行は破棄
      const [a, b] = pickTwo(free, rng);
      a.alive = false; b.alive = false;
      order.push([a.i, b.i]);             // 取り除いた順を記録
      remaining -= 2;
    }
    if (!ok) continue;                    // 失敗なら別シードで再試行

    assignKinds(tiles, order, kindCount); // ここで初めて絵柄を割り当てる
    for (const t of tiles) t.alive = true;
    // order を逆にたどれば必ず解ける = 解保証
    return { tiles, solution: order, attempts: attempt };
  }
  return null;
}

ポイントは、絵柄 (牌の種類) を最後に割り当てることです。取り除く順序 order が先に決まっているので、「同時に取るペア」には同じ絵柄を振ればいい。こうすると、どの盤も「フリーになった2枚を order の順に取れば必ず勝てる」ことが保証されます。面白いのは、この逆生成はほぼ一発で成功する点です。牌を1枚取ると必ずその周囲が開くので、途中で「フリーが2枚未満」になる破綻がめったに起きません。実測では平均試行回数1.0〜1.2回でした。前述の「作ってから解けるか判定する」方式の不確実さとは対照的です。

絵柄の割り当てが難易度を左右する

ただし、絵柄の割り当てには一工夫要ります。同じ絵柄の2ペア (4枚) が「連続で取れる位置」に固まると簡単すぎ、逆に散らばりすぎると読みにくくなります。私は2ペア単位でグループを作り、そのグループ順をシャッフルしてから位置に振ることで、絵柄が一箇所に固まるのを防ぎました。さらに、難易度を意図的に上下させたい場合は、解保証を保ったまま候補盤を複数生成し、「詰み罠の多さ」で採点して選びます。

// 同絵柄の縦積み=3点・横隣接=1点で「罠っぽさ」を採点
function trickiness(tiles) { /* ... */ }

function dealDifficulty(layout, kindCount, rng, level, samples = 10) {
  const cands = [];
  for (let i = 0; i < samples; i++) {
    const d = deal(layout, kindCount, rng); // どれも解保証つき
    if (d) cands.push(d);
  }
  cands.sort((a, b) => trickiness(a.tiles) - trickiness(b.tiles));
  const idx = Math.round(level * (cands.length - 1)); // level 0=易 〜 1=難
  return cands[idx];
}

候補はすべて deal() 産なので、どれを選んでも解けることは変わりません。変わるのは「取る順を間違えたときの詰みやすさ」だけ。難易度を上げても理不尽 (解が存在しない) にはならない、という設計にできたのが逆生成の恩恵です。

独立したソルバで「二重検証」する

ここで慎重になるべきなのは、「逆生成のロジックが正しい」と「生成された盤が本当に解ける」は厳密には別だということです。逆生成のコードにバグがあれば、解けない盤を「解ける」と言い張るかもしれません。そこで私は、逆生成とはまったく別ルートの独立ソルバを用意して、生成した盤を突き合わせました。深さ優先探索 (DFS) に置換表 (一度訪れた盤面を記録して枝刈り) を足したものです。

// 逆生成とは別実装。'solved' | 'unsolvable' | 'inconclusive' を返す
function solveForward(tilesIn, nodeCap = 300000) {
  const seen = new Set();     // 訪問済み盤面 (生存牌のビットマスク)
  let nodes = 0;
  function dfs(remaining) {
    if (remaining === 0) return 'solved';
    if (++nodes > nodeCap) return 'inconclusive'; // 探索打ち切り
    const key = stateKey();   // 生存牌の集合を BigInt で表現
    if (seen.has(key)) return 'unsolvable';
    seen.add(key);
    // フリーな同絵柄ペアを全部試す (4枚同時フリーは安全なので優先)
    for (const [a, b] of freePairs()) {
      a.alive = b.alive = false;
      const r = dfs(remaining - 2);
      if (r !== 'unsolvable') return r;
      a.alive = b.alive = true; // バックトラック
    }
    return 'unsolvable';
  }
  return dfs(aliveCount());
}

この独立ソルバを使って、4種類のレイアウト × 各2000シードを機械検証しました。チェック項目は「配牌が失敗した数=0」「記録した手順どおりに再生すると100%クリアできる」「独立ソルバが解なしと判定した盤=0」「行き詰まり救済のシャッフル後も解保証が崩れない=0失敗」。これが全部グリーンになって、初めて「解保証は成立している」と言えます。個人開発だと自分がテスターを兼ねる分、こういう別ルートの検証を持たないと「たぶん大丈夫」で出荷してしまいがちです。大きい盤ではソルバが探索上限で inconclusive (結論不能) を返すこともありますが、その場合も構成的証明 (手順の再生検証) が100%通っているので解の存在自体は担保されます。

「必ず解ける」のに詰むのが面白さの核

最後に、設計思想として大事だった点を1つ。解が存在することとプレイヤーが必ず勝てることは違います。盤に勝ち筋があっても、プレイヤーが違うペア同士で取ってしまう (クロスマッチ) と、そこから先が詰むことは普通に起きます。これはバグではなく仕様で、むしろこの「順番を間違えると詰む」緊張感がパズルの面白さそのものです。だから救済として「もどす (undo)」と「シャッフル」を用意し、シャッフルも同じ逆生成で配り直すことで、救済後も必ず解ける状態を保ちました。「開始盤は必ず解ける・ただし取る順を間違えると詰む・詰んだら救済できる」——この3点セットが、理不尽さと歯ごたえの境界線を決めています。

逆生成のいちばんの教訓は、「生成が難しい問題は、完成状態から巻き戻すと簡単な検証問題に変わることがある」という発想の転換です。ランダムに作って総当たりで確かめるのではなく、正しい手順を構成しながら作る。数独やナンプレの「完成盤から数字を抜く」生成とまったく同じ骨格で、生成型パズルを作るなら真っ先に検討する価値のあるパターンだと思います。