1.「三つ子」という新しいコンセプト
ナンプレに関して一風変わったコンセプトがあります。
今回はその話をしてみましょう。
いきなりですが、ナンプレを3問用意してみました。
図1-1 です。
まぁ……普通のナンプレですよね😅
1つは綺麗な対称形。ナンプレ誌などでは普通に見かける形。
そして、難易度は激辛ながらも3つとも解ける問題です。
至って普通のナンプレです。
しかし、実は、この3つには大きな秘密があります。
一体どんな秘密なのか?
合体させるとわかるので、ちょいと合体させてみましょうか。
おおぉ! ピッタリ!
ナンプレが完成してしまいました😃
これが、前図1-1 で述べた大きな秘密なんです。
詳細を述べましょう。
こういう仕組みです。
- 完成図にある81個の数字を3つのグループに分ける。
- それをヒント数字とみなすと、問題図が3つできあがる。
- その3問はすべて解ける。つまり唯一解を持つ。
まるで完成図から三つ子が生まれたような、そんな感じ。
その「三つ子を作る」というのが、今回のテーマです。
2022年1月9日。
ナンプレのフォーラムサイト『The New Sudoku Players' Forum』にて、興味深いアイデアが産声を上げました。
付けられた名前は「Troika Sudoku」。
「完成図を3つの問題図に分けることができるか?」という新しいコンセプトが Troika Sudokus. A challenge. というスレッドから誕生しました。
もちろん、ただ分けるだけではない。
次のようにクラス分けして美しい Troika も見つけたい、というわけです。
- 【Magic Trioka】
- どれも minimal で唯一解を持つ、3個一組のナンプレ。
- 【Perfect Troika】
- Magic Troika のうち、3つともヒント数字が27個である物。
- 【Sublime Troika】
- Perfect Troika のうち、3つとも何らかの対称形になっている物。
Magic は普通レベル、Perfect はさらに個数を揃えてグレードアップ、Sublime はさらに美貌も加わって最高級。
そんなところかな。
以降は Perfect と Sublime しか現れないので、みなさんはその2種類を頭の片隅においておくと良いでしょう。
ちなみに、sublime には「崇高な」「至高の」などの意味があります。
もしかして「完璧」を超えるようなニュアンスがあるのかな?
あ、「minimal」という新しいワードが出てきましたね。
これは「余分なヒント数字は無い」という意味です。
言い換えると「問題図のヒント数字をこれ以上減らすと解けない問題になってしまう」ということです。
ただ、みなさんは minimal をあまり意識する必要はありません。
「問題図に無駄がなく洗練されている」くらいの軽い認識でOKです。
さて、まずは軽いジャブを1つ。
Troika Sudoku を考案したスレッド主さんは、提案を投稿した翌日にもう Sublime Troika 寸前の物を披露していました。
図1-3 です。
おぉ〜、みんな綺麗に左右対称🥰
美人の三姉妹ですわ🥰
ただ、残念ながらこれらは3つとも minimal ではありません。
どれもヒント数字を何個か取り除いても解けてしまうというシロモノです。
だから Sublime 寸前。
本当に惜しい!
でも、逆に言えば、もぅ既にゴール近くまで来ているということです。
あとは minimal というハードルをクリアすればいい。
Troika Sudoku というアイデアが提案されたそばから、もぅ最高級レベルの傑物が見つかった。
これだけ早いと Sublime Troika の期待は高まって、すぐに見つかって議論が終わっちゃいそう?
果たして、議論の行方はどうなるか。
2.Perfect、発見!
いや〜、ホントに議論がすぐに終わりそうです😅
先述の Sublime 寸前の Troika が投稿された翌日、Perfect Troika が投稿されてしまいました。
しかも、その発見者さんは Perfect Troika を4組も見つけてた。
図2-1 はその中の1つです。
81個の数字が27個ずつに分かれている。
どのナンプレも唯一解を持っていて、minimal である。
しかし、対称形ではないから Sublime には届かない。
ものの見事に Perfect Troika です。
親記事投稿から3レス経ったらもぅ Perfect。
登山で言えばもぅ8合目。
あまりに健脚すぎやしませんか?😅
……とまぁ、ここまで読むといとも簡単に Perfect Troika が発見されたように見えますね。
しかし、実際はそんなことはありません。
実は、3分割で問題図を作るにあたってかなりの困難が待ち受けていました。
その困難を説明するために、まずはナンプレの作り方について話をしましょう。
ナンプレの作り方はいくつかありますが、その中の1つに「完成図から数字を消す」という方法があります。
実際に問題を作ってみました。
図2-2 左側の完成図を用意し、そこから24個の数字を選び、他のマスの数字をすべて消す。
そうしてできたのが 図2-2 右側の問題図です。
もちろん、ちゃんと解けます。
単に「ナンプレの問題を作る」という点では、この方法は非常に簡単です。
数字をたくさん残しゃぁいいんだもの😅
ヒント数字が40個も50個もあれば、まぁ高確率で唯一解を持つでしょう。
完成図を作ってしまえば、問題はもぅ8割方できたも同然なんですね。
前図2-1 の発見者さんは、この数字消去法で Troika を作ることを考えました。
大まかな方針は、まずは特殊な完成図を用意し、その完成図から数字を27個選んで第1の問題図を作り、残り54個の数字から27個選んで第2の問題図を作り、最後に残った27個が第3の問題図になる。そういう要領です。
これで3問とも唯一解を持って minimal な問題図であれば、晴れて Perfect Troika 完成! ……となるわけですね。
「特殊な完成図」については、図2-4 で後述しましょう。
ただ、残念ながらこの数字消去法にはいくつかの欠点がある。
製作者のアイデアや作意を盛り込めない。見た目美しい問題図にしにくい。etc...
特に、Troika 作成に関しては次の欠点が強烈なハードルとして立ち塞がるんです。
そこそこ数字を残しても、唯一解を持ってくれないことが多い。
中級程度のナンプレ問題には24個程度の数字が配置されています。
しかし、上記の方法で数字24個の問題を作るというのは結構大変です。
なんせ、テキトーに数字を残して問題図を作っても「数字が1マスも埋まんねぇ😅」なんてことはザラにある。
数字選びには試行錯誤が山ほど必要なんですね。
(事実、図2-2 の問題作成には結構な時間がかかった)
唯一解を持ってくれない理由はあります。
ナンプレの完成図には次の厄介な性質があるからです。
どの完成図にも「別解のタネ」がそこら中に潜んでいる。
一般的なナンプレの完成図は数字が不規則に並んでいます。
だから、タネは形も大きさも多種多様。
図2-3 のような4マスの物は最小で、6マス以上のタネもたくさんある。
2種類の数字をすべて含む大量18マスのタネもある。
盤面にもよるけれど、こういったタネは盤面に300〜500個ほど分布しています。
どこにどう散らばっているのかわからないタネ達を1つも残さず排除して問題図を作るというのは、まぁ〜それはそれは大変なんですね。
ましてや、Troika 作成となれば苦労は3倍。至難の業なんです。
ただ、ここでちょっとだけ朗報がある。
実は、すごく単純なタネ分布を持つ完成図が存在します。
それが 図2-4 です。
この盤面、なんとな〜く数字が綺麗に整列してるっぽく見える。
その見た目通りの大きな特徴があります。
ブロック3個並んだヨコ長3×9マス領域を見てみましょう。
その領域をブロック単位で見ると、123はトリオのまま斜めに移っていますね。
456も789も同様にトリオを保っている。
タテ長9×3マス領域も同じ。147、258、369が仲良くトリオ。
数字の並びがすごく単純でわかりやすい!
このように、どの3×9領域(タテ長ヨコ長問わず)にもトリオが必ず3回ずつ現れている盤面が存在します。
これを canonical grid と呼びます。
これは most canonical grid と呼ばれることもあり、MC grid という略称も存在します。
当ページでは MC グリッド と呼ぶことにしましょう。
さて、この MC グリッド。
数字の並びが単純だと言いましたが、これは一体何を意味するのか?
それは、こういうことなんです。
別解のタネも並びが単純になる。
そのおかげで、小型のタネが急増する。
図2-5 の赤色や青色のように、タネの大半は3列に単純に並びます。
そのようなタネは最大でも9マスで、その場合は必ず「三」の字になる(黄色)。
盤面にはハンバーガーアイコンのような小さいタネが規則的に分布する。
こういう特徴があるわけですね。
実は、図2-1 の完成図は MC グリッドです。
図2-1 の発見者さんは「小型のタネを多数持つ完成図の方が Troika を見つける可能性が高い」と予感していたそうで、MC グリッドに目を付けていました。
その予感は正解だったようですが、それでもタネが盤面に大量に存在することは変わらず、Perfect Troika の作成は非常に手間のかかる作業でした。
事実、成功までに膨大な試行錯誤を経ています。
1つの MC グリッドからヒント数字27個の問題図(唯一解を持ち minimal な物)を大量に作り置きして、それらを使って作業をした。
最初は30万個だったストックを300万個にまで広げ、Troika 発見に精力を注いでいましたね。
そのペアは54マスを占有しますが、完成図からその54個の数字を消すと第三の問題図ができあがります。
それが唯一解を持ち、かつ minimal であれば、めでたく Perfect Troika の完成となるわけです。
これを該当ペアすべてに対して調べたわけですが、なんと、ペアの総数は2000万組を超えていたという!
一連の作業をすべてコンピュータに任せるのは当然としても、気が遠くなる作業なのは間違いない。
実際、その300万個の中から見つかった Perfect Troika はたったの104組だったそうです。
まるで砂金採り😅
ちなみに、当の発見者さんは MC グリッドでない盤面に対しても同じ挑戦をしていました。
そして、諸々の調査の結果、次の推測に至ったようです。
- 「ほぼ間違いなく、どの完成図にも Perfect Troika が大量に存在する」と言ってよさそう。
必ず大量に砂金が見つかる砂金採り。
こう聞くと、すっごく夢が広がるね😅
3.美しい Troika 達
Troika の議論が進むにつれ、スレッドにはたくさんの例や考察が寄せられました。
その中で美しい形の Troika(図3-1 を除く)も生まれたので、ちょいとご紹介。
このセクションは、文章を読むより図をパパッと見ていってください😊
いや〜、いきなり美しすぎる形🥰
しかし、残念ながらこれは Suplime Troika にはなれませんでした。
3問とも minimal ではないからです。
ただ、3問合わせても余分なヒント数字はたった4個しかありません。
だから本当に惜しかった。
図3-2 はナンプレ上級者なら理解できる Perfect Troika です。
この3問、すべて本質的に同じ問題図です。
外見は違うけど性格がまったく同じ三つ子、といったところでしょうか。
次の4つを施しても本質的に同じ構造の盤面ができあがる、ということがナンプレ界では知られています。
- 数字を置換する。
- band を置換する。または stack を置換する。
- band 内のヨコ列を置換する。または stack 内のタテ列を置換する。
- 盤面を回転・裏返しする。
ちなみに、本質的に同じ構造であることを数学では「同型」と言います。
Troika スレッドの内部では「isomorphism」という単語が割と現れて、数学の視点でも議論が活発に行われているんですね。
そして、ついに Sublime Troika 現る!
この3問はヒント数が27個であり、対角線で線対称になっています。
ついでに言うと、前図3-2 で説明した「同型」でもあります。
よく見ると、どのタテ列・ヨコ列・ブロックにも数字が3個ずつありますね。
あちこちで数字がL字に並んでいて見た目も模様のように綺麗🥰
Troika の議論の最終結論と位置づけても良いかもしれませんね。
4.さらに苦難の道へ……
Troika の活発な議論が行われているさなか、実は、1つの提案が起きていました。
完成図を4つの問題図に分けることはできますか?
なんと、子供をもう1人増やせという!
今まで Troika 発見に燃えていた猛者達はこの四つ子を「Quadriga」と名付け、さらに苦難の道を歩んでいくのでした。
議論の場は Quadriga Sudoku という新しいスレッド。
そのスレッド主さんは、まず手始めに自分の成果を5組披露しました。
そのうちの1つが 図4-1 です。
完成図がちゃんと4つに分割されている。
これで Quadriga 完成か……と思いきや、図の右下に何やら巨大な数値が書かれている。
この数値、解の個数です。
黄色の問題図は唯一解を持っていない。なんと 9916331 個の解がある!
他の3問にしっかり唯一解を持たせたら、こんなにも黄色にしわ寄せが来ちゃってた😅
そういや、セクション2ではナンプレの作り方・数字消去法の話をしましたっけ。
数字をたくさん残しても唯一解を持ってくれないことが多いわけです。
なのに、四つ子に求められるヒント数は平均で 81÷4=20.25 個。
Perfect Troika の27個ですら別解の山を築いていたのに、今度は「さらに少ないヒント数で唯一解を持て!」と言ってきた。
もはや無謀な要求である😅
しかし、そこはナンプレフォーラムの猛者達、991万個から個数を驚異的に減らしていく。
15000個、7000個、2600個、516個、そして、ついに「2個」にまで到達した。
ゴールテープまで本当にあと一歩という躍進を見せたのです。
結論を言うと、Quadriga の発見は成功しました。
図4-2 です。
問題図のヒント数字はそれぞれ 17個, 19個, 22個, 23個。
どれも解ける問題です。
Quadriga を作る基本方針は、「なるべく少ないヒント数の問題図を先に作る」です。
最初に苦労しておけば後がラクになる、と似たようなものかな?
最初の2問はヒント17〜19個程度で作り、残りの数字達を分割して2問同時に作るという手法をとりました。
その手法は基本に忠実、とにかく地道なものでした。
与えられた完成図からヒント17個の minimal な問題図をすべて作る。ヒント18個の物もすべて作る。19個以降も同様。各個数ごとに問題図のストックを用意した。おそらく22個くらいまで用意した。
そして、数字を1マスも共有しない問題図2つをストックから見つけ、残りの数字から別の2問を探していきました。
図4-2 で言うと、赤色&青色の問題図をストックから見つけ、残り45マスの数字を試行錯誤で二分しまくって緑色&黄色を見つけたわけです。
もちろん、Troika と同じく「別解のタネ」に大いに悩まされながらの道のりでした。
その分、スレッドではタネに関する濃い定理も導かれてましたね。
「最小の別解のタネは4マス。そのタネは1マスずつ4問に分散されなきゃいけない」
「図4-1 で言えば、赤色&青色を抽出した後の残りは45マス。45マスを二分しなきゃいけないから、45個のうちどの数字1個を除去しても解ける問題でなければいけない」
定理の内容が難しいのでここでは説明しませんが、興味のある方々は当該スレッド Quadriga Sudoku をご覧ください。
とにかく、彼らは濃い議論を交えながらも道なき道を邁進していたということです。
そんなこんなで、盤面からめでたく四つ子ができた。
三つ子・四つ子が成功したとなると、やっぱり「五つ子」なんてものも気になりますね。
果たして、五つ子は可能なんだろうか?
結論を言うと、残念ながら五つ子は絶対にできません。
次の定理が知られているからです。
- ヒント数字が16個以下であるナンプレ問題には、必ず別解がある。
完成図を5分割すると、ヒント16個以下の問題図が必ずできちゃうんです。
ヒント数の平均は 81÷5=16.2 だから、どれかの問題図はヒント16.2個以下ですもんね。
この定理は2012年発表の論文で証明されています。
セクション2で触れた「別解のタネ」に注目して複数解を考察し、それを活かしてコンピュータで定理を導いています。
この論文(2013年9月改訂版)は学術記事サイト『arXiv』のこのページでダウンロード可能です。
興味があれば是非。
五つ子以降がダメなら、逆に「双子」はどうか?
たぶん、これは議論する余地はほとんどなさそう。
試行錯誤で40個と41個に分ければ、まぁどっちも解ける問題図になっていそうです。
しかし、どっちもヒント数字が大量だから、たぶん minimal にはなってなさそうです。
双子は……無理かな?
troika, quadriga ときたら双子は「biga」になるんだろうけど、ナンプレ界には Biga は存在できなさそうです。
参考・参照
- The New Sudoku Players' Forum, 『Troika Sudokus. A challenge.』,
http://forum.enjoysudoku.com/troika-sudokus-a-challenge-t39718.html - The New Sudoku Players' Forum, 『Quadriga Sudoku』,
http://forum.enjoysudoku.com/quadriga-sudoku-t39738.html - Gary McGuire/Bastian Tugemann/Gilles Civario 著,
『There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration』,
https://arxiv.org/abs/1201.0749v2
更新履歴
- 2023.12.16.
- 新規公開。