数独 生成 - パズル自動生成アルゴリズムの設計思想

数独パズルの生成は 3 つのステップで行われる。(1) 有効な完成盤面をランダムに生成する。(2) 完成盤面からセルを 1 つずつ除去し、除去後も唯一解が保たれることを検証する。(3) 除去後のパズルの難易度を分析し、目標難易度と一致するか確認する。ステップ 2 と 3 が品質を決定する核心部分であり、ここに計算コストの大部分が集中する。

パズルとして成立するためには、解が唯一でなければならない。セルを除去するたびに、残ったパズルが唯一解を持つかどうかを検証する必要がある。この検証には、ソルバーを使って解の数を数える。解が 2 つ以上見つかった時点で「唯一解ではない」と判定し、そのセルの除去を取り消す。この検証は計算コストが高いが、パズルの品質を保証するために不可欠である。

難易度は、パズルを解くために必要なテクニックの複雑さで定義する。生成したパズルに対して人間の解法をシミュレートし、どのテクニックが必要かを分析する。ネイキッドシングルだけで解ければ Easy、ヒドゥンシングルが必要なら Medium、ネイキッドペアが必要なら Hard、X-Wing が必要なら Master と分類する。目標難易度と一致しない場合は、パズルを破棄して再生成する。

デイリーチャレンジのように「全ユーザーが同じパズルを解く」機能を実現するには、乱数生成器にシード値を与えて再現性を確保する。日付からシード値を計算し、同じシードからは常に同じパズルが生成されるようにする。これにより、サーバーにパズルを保存する必要がなく、クライアント側で同じパズルを再現できる。

完成盤面からセルを除去する際、除去の順序と対称性が生成パズルの質と見た目を左右する。最も単純なのはランダムな順でセルを 1 つずつ外し、唯一解が壊れたら戻す方法だが、これだとヒントの配置が不規則になりやすい。多くのパズルは点対称になるよう、中心を挟んだ 2 マスを同時に除去する。これにより伝統的な数独らしい美しい配置が得られる。除去を進めるほど唯一解の検証コストが上がるため、除去候補の順序を工夫して早期打ち切りを増やすと生成が速くなる。除去できるセルがなくなった時点が、そのパズルの最小ヒント構成に近い状態となる。

生成で最も厄介なのが難易度の推定だ。難易度は「必要なテクニックの最高難度」で定義することが多いが、同じパズルでも解き手の手順によって体感難易度は変わる。さらに、必要テクニックを一段上げるだけで体感難易度が跳ね上がるなど、段階が線形でない。実装では人間の解法を模したソルバーで、ネイキッドシングルだけで解けるか、ヒドゥンシングルが要るかを順に判定し、最初に詰まる段階で難易度を決める。ただしこの判定はソルバーが実装したテクニックの範囲に依存するため、未実装のテクニックがあると難易度を過大評価することがある。一貫した難易度表示には、ソルバーのテクニック網羅性が欠かせない。

生成の計算コストの大半は唯一解の検証に費やされる。素朴に全探索すると遅いため、実用的な生成器ではいくつかの工夫を用いる。候補数が最も少ないマスから順に試す制約伝播を組み込むと、無駄な分岐を大幅に減らせる。解の数を数えるソルバーは 2 つ目の解が見つかった瞬間に打ち切るようにし、すべての解を数え上げない。さらに、Dancing Links (DLX) のような厳密被覆問題向けのアルゴリズムを使うと、バックトラッキングが効率化される。生成は重い処理だが、デイリーチャレンジ用に 1 問だけ作るならクライアント側でも十分実用的な速度で動く。

生成器が目指すべきは、ただ唯一解を持つだけでなく、解いていて楽しい良問だ。良問の条件には、論理だけで最後まで解けること、行き当たりばったりの試行錯誤を強いないこと、そして難易度表示と実際の手応えが一致していることが含まれる。これらを満たすため、生成後にソルバーで解き筋を再現し、当て推量が必要な箇所がないか、想定どおりのテクニックで解けるかを検証する。条件を満たさないパズルは破棄して再生成するため、目標難易度が高いほど生成にかかる試行回数は増える。量産よりも一問ずつの品質を重視する設計が、結果として遊ぶ人の満足度を高める。ヒントの数だけを基準に難易度を決めるのは誤りで、少ないヒントでも素直に解ける問題もあれば、多くのヒントでも高度なテクニックを要する問題もある点に注意が必要だ。