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

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

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

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

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