0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

ナンローを解く — 数字は「選ぶ」ものではなく「数える」もの。ヒント1個は独立した2つの事実で、片方だけでは何も解けない

0
Posted at

ナンロー (Nanro) を、5 つのルールセット内蔵でブラウザに実装した。盤面は領域に分割されている。いくつかのマスに数字を書き、残りは空白にする。①どの領域にも数字が最低 1 つ、②領域内の数字は全部同じで、その値はその領域で数字が入ったマスの個数に一致、③数字マス全体が 1 つに連結、④どの 2×2 も全マス数字にはならない、⑤領域境界をまたいで隣り合う数字マスは異なる数字。ソルバー内蔵パズル第 43 弾。

デモ: https://sen.ltd/portfolio/nanro/
リポジトリ: https://github.com/sen-ltd/nanro

Nanro

数字は選ぶものではなく、数えるもの

ルール②がこのパズルの人格の全てだ。領域のラベルはその領域が塗った個数そのものなので、数字は自由変数ではない。答えは「数字マスの集合 S」だけで完全に決まり、ラベルは関数 領域 r ↦ |S ∩ r| として自動的に付いてくる。

だからこの実装にはテンキーがない。プレイヤーはマスをマークするだけで、画面の数字はその領域の現在の個数のライブ表示だ。1 マス変えると領域の数字が一斉に動く。ソルバーも同じ形で、変数は「マスごとの 2 値(数字/空白)」+「領域ごとのラベル(個数が確定させる)」。探索が「数字か空白か」だけで分岐して完全になるのはこの構造のおかげだ。

ラダーは 5 段:

レベル ルール
count 領域算術: 確定数 ≤ ラベル ≤ 確定数 + 未定数、およびその両端の飽和(上端到達なら残りは空白、下端到達なら残りは全部数字)
block + どの 2×2 も全数字禁止(3 つ埋まったら 4 つ目は空白)
clash + 等しいラベルは領域境界をまたいで接触できない(伝播は両向き: 片側確定なら他方から消す/同ラベル確定同士なら片方が数字なら他方は空白)
reach + 連結性: 確定数字マスに届かない成分は死ぬ、確定群の関節点は数字確定(lowlink DFS 1 回で全部出す)
probe + 1 マス仮置き → reach まで fixpoint → 矛盾したら棄却

ヒント 1 個は独立した 2 つの事実

盤面に印刷された数字は、実は2 つの別々のことを同時に言っている:

  1. このマスは数字マスである(位置の情報)
  2. この領域の個数は v である(値の情報)

そしてこの 2 つは独立に配れる。実装では clue を 3 モードに分けた(full / 位置だけの MARK / 領域ラベルだけを渡す labelHints)。同じ答え・同じヒント位置で片方の半分だけを伏せると何が起きるか——連作で初めて、ヒントを半分に割って各半分の値打ちを測った

答えの数字マス全部をヒントにした上(q = 1、つまり「答えをそのまま印刷した」状態)で片側を伏せた一意率:

盤面 完全なヒント 位置だけ 値だけ
5×5 100.0% 36.0% 1.5%
6×6 100.0% 17.5% 0.5%
8×8 100.0% 8.7% 0.0%
10×10 100.0% 3.0% 0.0%

値だけの盤面は事実上壊滅する。全領域のラベルを開示しても 5×5 で 1.5%、8×8 以上では 0.0%。幾何を消した算術には何も残らない。

面白いのは位置だけの側も無料ではないことだ。「答えの数字マスを全部教える」のに 8×8 で 8.7%、10×10 で 3.0% しか一意にならない。理由を口に出すと当たり前で、「このマスは数字マスだ」は「他のマスは数字マスではない」を一言も言っていない。数字マスが増える方向の別解が生き残る。

そして両方を戻すと、同じヒントマスで 100%。情報はどちらの半分にもなく、その論理積にある。ヒント密度を落とした q = 0.8 でも同じ形で、8×8 は full 24.0% に対し位置だけ 0.0%・値だけ 0.0% だった。

ヒント予算を決めるのは作者ではなく答え

ナンローではヒントは答えの数字マスの上にしか置けない。空白マスに印刷する数字が存在しないからだ。つまりヒント予算は作者が回すダイヤルではなく、答えの性質である。

盤面 領域数 答えの数字マス 盤面に占める割合 2×2 則の上限 probe が要求する割合
6×6 11.7 21.3 59.2% 75.0% 34.3%
8×8 20.7 38.0 59.3% 75.0% 32.1%
10×10 32.2 58.3 58.3% 75.0% 32.4%

合法な答えは盤面の 58〜59% を数字にする(2×2 禁止の上限は 75%)。ラダーはそのうち約 1/3 の開示を要求する。最小化したヒント数の中央値:

盤面 答えの数字マス count block clash reach probe
6×6 21 17 14 14 9 8
8×8 38 32 25 24 16 13
10×10 59 49 38 37 24 19

そして予算は使い方が全てだ。10×10 を一意にするのに敵対的に選べば 19 個で足りるが、同じ 19 個をランダムに配ると 30 盤中 0 盤しか一意にならない(6×6 の 7 個、8×8 の 12 個でも同様に 0.0%)。

ablation と increment が逆符号でぶつかる

生ストリーム(ランダム分割+合法な答え 1 つ+数字マスの割合 q をランダム開示、一意性で条件づけない)で段を足していくと:

盤面 q count +block +clash +reach +probe 一意率
6×6 0.8 3.6% 12.0% 12.8% 32.4% 40.8% 40.8%
6×6 0.9 24.8% 38.0% 41.6% 58.4% 65.6% 65.6%
8×8 0.9 6.0% 14.0% 16.5% 37.5% 45.5% 45.5%
10×10 0.9 0.7% 6.0% 7.3% 21.3% 24.7% 24.7%

増分で読むと clash はほぼ乗客だ。8×8・q=0.9 で +2.5pt、最小ヒント表でも 25 → 24 の 1 個しか稼がない。ところが同じルールを probe ラダーから抜くと(ablation は列が潰れないようサイズごとに少し濃い q で回している):

盤面 full −count −block −clash −reach
6×6 64.0% 0.5% 49.5% 52.0% 44.5%
8×8 69.3% 0.0% 53.3% 50.0% 40.0%
10×10 54.0% 0.0% 37.0% 36.0% 24.0%

8×8 で −clash は 19.3pt 失う。単独では 1 マスも進めないルールが、抜くと盤面の 5 分の 1 を持っていく。理由は明快で、**probe が必要としているのは「前進するルール」ではなく「反駁するルール」**だからだ。clash はこの盤面で最も安価な矛盾検出器で、仮置きを殺す仕事を一手に引き受けている。アクレ (#322) の quad と同型の現象が、今回は「増分でわずかに稼ぐのに ablation で急所」という中間的な顔で出た。

count はヒントを読む唯一のルールなので、抜けば全崩壊(0.0%)。これはケイブ・ぬりみさきと同じ形だ。

連作の教訓——ablation だけ読むと本質が無駄に見え、増分だけ読むと無駄が本質に見える——が、今回は「増分では乗客・ablation では急所」という 3 例目のパターンで再現した。

1 マス領域の分割は「難しい」のではなく「違法」

作者が本当に所有するダイヤルは 1 本、領域の粒度だけだ。n=8・q=0.9 で回すと:

領域サイズ 試した分割 合法な答えを持つ分割 領域数 数字マス率 count +reach +probe 一意率
1–1 120 0
1–2 120 0
2–2 120 120 29.4 64.9% 6.7% 45.8% 80.0% 80.0%
2–3 120 120 24.0 61.3% 9.2% 36.7% 54.2% 54.2%
2–4 120 120 20.8 58.9% 7.5% 25.8% 38.3% 38.3%
3–5 120 120 14.6 54.6% 4.2% 31.7% 40.0% 40.0%
4–7 120 120 10.4 52.1% 6.7% 20.8% 27.5% 27.5%

上 2 行の 0 は測定というより定理だ。サイズ 1 の領域はラベルが 1 しか取れず、そのマスは必ず数字になる。全マスがサイズ 1 の領域なら全マスが数字マスで、2×2 が丸ごと埋まる——n ≥ 2 で合法盤面は 1 つも存在しない(ついでに隣接する 1 マス領域同士はラベルが両方 1 で clash にもかかる)。粒度ダイヤルを最小に回すと、パズルは難しくなるのではなく消える

逆に粒度を上げると一意率は 80.0% → 27.5% へ単調に落ちる(3–5 で一度戻るのは領域数の減少と領域内自由度の増加が競合するため)。連作の他のパズルでは粒度ダイヤルが「100% から 0% まで掃く崖」だったが、ナンローでは片端が崖ではなく壁である。

probe ⇔ 一意の法則は 2,400 盤中 1 盤で破れた

この連作には「probe fixpoint が完答する ⇔ 解が一意」という経験則がある(probe ⇒ 一意は健全性から定理、逆は測定)。ナンローはセクション A の全 2,400 盤中 2,399 盤で成立し、1 盤で破れた: 8×8・q=0.7 の 1 枚が、一意なのに probe ラダーが止まる。

この 1 枚はラダーとコードを共有しない生エンジンで再確認した。ナンローの生エンジンは定義そのものを歩ける: 領域のラベルは個数なのだから、領域の空でない部分集合を選ぶことがラベルを選ぶことでもある。したがって全探索空間は領域ごとの 2^size − 1 の直積で、これを領域単位で列挙し、葉ごとにルール文(バリデータ)で採点する。結果は解数 1・5,029 ノード・cap なし——伝播探索と一致した。

エンジン突き合わせは全体で 614/614 一致(生エンジンの cap 到達 1 盤、伝播側の cap 到達 34 ラン は「一致」ではなく「スキップ」として明示報告)。

生成と bank

生成にパズルレベルの探索は要る(ランダム分割から合法な答えを 1 つ引く)が、これは伝播つきランダム化 DFS にノード上限 4,000 と Las Vegas リスタートを付けて済む。答えが出たあとは、目標レベルが完答するまで数字マスをランダム開示 → 不要なヒントを全部取り返すという定番の最小化で、grade は「完答できる最弱のレベル」。分割も答えも grade 間で動かさず、動くのはヒント集合だけだ。

bank は 75 盤(6×6 / 8×8 / 10×10 × 5 グレード × 5 枚)で、全サイズ全グレードが埋まった。出荷前に探索エンジンで一意性を再証明している。

テストは 35 本。ハンド盤面(5×5・9 領域・6 ヒント・reach が必要な一意盤)、2×2 盤の合法盤面 4 通りを手で数えて両エンジンに突き合わせる、各ルールの単体手筋、どのレベルでも真の答えが候補から消えないことの性質テスト、ラダーの入れ子性、最小ヒント集合の各ヒントが load-bearing であること、そして bank 全盤の grade と一意性。

まとめ

  • 数字を選ばず数えるパズルでは、答えは集合 S だけで決まり、ソルバーの変数もヒントの形もそれに従う
  • ヒント 1 個は位置と値の 2 つの事実で、値だけでは 0〜1.5%、位置だけでも 3〜36%、両方で 100%——情報は論理積にある
  • ヒントは答えの数字マスの上にしか置けないので、予算を決めるのは作者ではなく答え(盤面の 58〜59%、その約 1/3 を要求)
  • 増分ではほぼ乗客の clash が、ablation では 19.3pt の急所——probe が欲しいのは前進ではなく反駁
  • 1 マス領域への分割は難しいのではなく違法(2×2 則で合法盤面が消える)
  • probe ⇔ 一意は 2,400 盤中 1 盤で破れ、その 1 枚を生エンジンが 5,029 ノードで再確認

ソルバー内蔵パズル第 43 弾。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?