数独の難易度はどう決まるのか
ヒント数が当てにならない理由、「必要になった一番難しい手筋」で格付けするとはどういうことか、そして同じヒント数の二問がまるで別物になる理由。
空きマスが多いほど難しい、と多くの人が考えています。もっともな推測ですが外れています。だから「エキスパート」の盤面が五分で崩れ、「やさしい」の盤面がどうしても動かない、という経験が広く共有されているわけです。
数独の難易度とは、その盤面がどんな種類の推論を要求するかであって、どれだけ欠けているかではありません。
ヒント数が誤解を招く理由
ヒント数が同じ二つの盤面を考えます。片方はヒントの配置のおかげで各手が隠れ単数になる。どの時点でも、ある数字がある単位で置ける場所が一つしかなく、問題はファスナーのようにほどけていきます。もう片方は同じ数の手がかりで、簡単な二十手のあとすべてが止まり、唯一の出口が二行二列にまたがる形だけになる。
離れて見れば両者は同じに見えます。片方は四分、もう片方は四十分。空きマスを数えても両者は区別できません。
逆方向も同じです。ヒントが24個でも単数候補だけで最後まで進む盤面はありますし、32個あっても X-Wing が要る盤面もあります。まばらであることは難しさではなく、見た目の威圧感です。
本物の下限はあります。ヒント17個未満の数独には解が一つになるものが存在しません。McGuire、Tugemann、Civario による 2012 年の全数探索の結果です。ただしそれは問題空間全体への制限であって難易度の物差しではありません。ヒント17個の配置の大半は解が多数あり、そもそも問題として成立していません。
ましな指標：解くのに何が要ったか
体感と本当に対応するやり方は、人と同じように解いてみて、それに何が要ったかを記録することです。
ソルバーは人間の手筋の連鎖を、必ず安いものから順に回します。単数候補、隠れ単数、指差し、囲い込み、裸のペア、隠れペア、裸のトリプル。そのあとに形の手筋、X-Wing、Swordfish、XY-Wing。一手取れるたびに先頭へ戻り、また一番安いものから試します。確定が一つ入るだけで、高い手筋が不要になることが多いからです。
盤面が埋まったとき、意味を持つ数字は一つです。この連鎖が到達した最も高い手筋。それが等級です。ある瞬間に隠れペアが一度だけ必要で、それ以上は要らなかった問題は、その前後にどれだけ簡単な手が並んでいても隠れペアの問題です。
体感とよく一致します。実際に足を止めさせているものを測っているからです。盤面の難しさは、そのなかで最悪の一瞬で決まります。
五つの帯
Sudoku - Calm Number Puzzle はまさにこのやり方で格付けしていて、五段階はヒント数のしきい値ではなく手筋の梯子を区切ったものです。
- 入門 — 単数候補のみ。どの手も、可能性が一つしかないマス。
- やさしい — 隠れ単数が加わる。ある単位で置き場所が一つしかない数字。
- ふつう — 指差し、囲い込み、裸のペア。
- むずかしい — 隠れペアと裸のトリプル。
- エキスパート — X-Wing、Swordfish、XY-Wing。
等級が「使えたかもしれない手筋」ではなく「必要だった手筋」なので、この帯には具体的な意味があります。むずかしいの問題は X-Wing を一度も使わずに終えられますが、これは幸運ではありません。X-Wing が必要な盤面はエキスパートに格付けされ、むずかしいとして配られることがないからです。
帯を狙って作るということ
格付けは半分にすぎません。もう半分は、狙った帯に着地する問題を実際に作ることです。
工程は完成盤から始まり、マスを取り除いていきます。180度回転で対になる二マスずつ抜くので、出来上がりが問題らしい見た目になり、でたらめに散らしたようにはなりません。取り除くたびに二つの検査が走ります。一つ目、ソルバーが解の個数を上限二で数える。ちょうど一つでなければその除去は即座に取り消し。二つ目、あらためて格付けし、その二マスで狙った帯を越えてしまったなら、これも取り消し。
対称のパスで難しさが足りなければ、非対称に一マスずつ掘る二周目が走り、目標の帯に届くまで続きます。各段階にはヒント数の下限もあり、入門の40からエキスパートの22まで。これは「やさしいなのにヒントが26個しかなく、しかも単数候補だけで解ける」という、格付けは正しいのに見た目が妙な問題を避けるためです。
出来上がった等級が指定と合わなければ、その問題は破棄して次の種でやり直します。だから格付けは安くなければなりません。合格する問題を一つ作るとは、格付けを何度も走らせるということだからです。
それでも難易度が個人的に感じられる理由
測られた等級が言うのは「どの手筋が必要か」であって「あなたが何分かかるか」ではありません。数字単位で走査する人は隠れ単数をすぐ見つけ、やさしいの盤面を一気に抜けます。マス単位で考える人は同じ問題に時間を取られ、これはやさしくないと言い張ります。二人が語っているのは探索の腕であって、問題ではありません。
だからこそ「どの段で止まるか」は、次に何を学ぶべきかの優れた指針になります。帯が手筋の名前をそのまま指しているからです。むずかしいで止まるなら隠れペアと裸のトリプル。エキスパートで止まるなら X-Wing と XY-Wing です。
よくある質問
ヒントが少ないほど難しいのですか
当てになりません。ヒント数は大まかな見た目の印象と、一意性のための17という固い下限を決めるだけです。ヒント24個の盤面が単数候補だけで解けることもあれば、32個の盤面が X-Wing を要求することもあります。難易度を決めるのは必要な手筋です。
一番難しい数独の手筋は何ですか
上限はありません。チェーンや強制ネット、一意性を使う論法はいくらでも積み上がります。格付けされた問題については、多くのアプリが割に合わなくなるあたり——X-Wing、Swordfish、XY-Wing 付近——で止めています。それ以上は、ほとんどの人にとって楽しくなくなります。
同じ問題なのにアプリごとに難易度が違うのはなぜですか
実装している手筋の集合と順序が違うからです。隠れペアを実装していないアプリは、それが必要な盤面でもっと高い手段を使うしかなく、結果として高く格付けします。等級は、それを生んだ梯子の上でしか意味を持ちません。
エキスパートは必ずむずかしいより難しいですか
むずかしいが必要としない手筋を必ず要求します。それでも所要時間は短いことがあります。エキスパート級の一手が序盤に来て、その後が素直な場合です。等級は推論の天井の話で、長さの話ではありません。
実際の問題で試す
Sudoku - Calm Number Puzzle は、解くのに実際に必要な一番難しい手筋で難易度を決め、盤面を見せる前に解が一つであることを検証し、ヒントでは数字を埋めるだけでなく手筋の名前を答えます。無料、オフライン、広告なし、アカウントなし。