ぼくのかんがえたさいきょうのパズル
これはペンシルパズルⅠ Advent Calendar 2020一日目の記事です。
utimeです。
1. スケルトン
早速ですが、まずは以下のパズルを解いてください。東大パズ同が今年の５月祭で出した冊子の別紙「ハバネロ」に載せたものと同じです。
リストコピペ用
解けた方、解けなかったけど忙しい方......3. へ進む
解けなかったし忙しくない方........................2. へ進む
2. 想定解
①まずは盤面を探します。スケルトン盤面らしきものが見つかりませんが、よく見ると左のマス目が盤面であることがわかります。
②次にリストをざっと見ます。「BとNって何だよ。」と思います。
③もう一度リストをじっくり見ます。「実はこの中にBの個数とNの個数が違うものがあって、そこがとっかかりになればいいなぁ。」と期待します。
④ ③の淡い期待が裏切られます。が、一応考察します。Bが1個多い単語と1個少ない単語があれば、どちらも縦(または横)になることが分かりますが、徒労に終わります。
⑤逆に、BもNも6個ずつだからこそ成り立ちそうな性質を探します。横1行目にはBが6個、Nが6個入ることが確定しているので、縦の単語12個のうち、1文字目は6個がB、6個がNであると分かります。
これはどの行についても成り立つので、これらの情報をうまく使えば縦の単語12個の組が決まりそうな予感がします。
⑥ここで数値的に考えます。BとNにそれぞれある整数を割り当てると、縦の単語12個の和が(B+N)×6×111,111,111,111となることが分かります。情報量としては、各行の文字が6個ずつであるという情報×12行分を、和の情報1つだけに落としてしまったのですが、実は、落ちた情報は繰り上がりっぽい内容だけなので(多分)、この情報だけでも、縦の単語12個の組が何なのか1パターンに定まるくらいには強そうです
⑦ここで2つの問題が浮上します。(i)B、Nに何を割り当てるか (ii)どのようにして12個の組を求めるのか
⑧(ii)について先に考えます。競技プログラミングに馴染みがある方は分かるかと思いますが、この問題は一般には人力では解決できないです(多分)。
⑨でもここまでの解き筋はよさそうなので、諦めるには早そうです。(ii)で、人力で解が見つかる場合があるからです。例えば、3の倍数が22個、3で割って1, 2余る数がそれぞれ1個ずつであれば、縦12個の組の和も横12個の組の和も同じなので、3で割り切れない数が同じ組に入ると確定します。
一般に、十分大きい整数pで割ったとき、a余る数が12個、b余る数が11個、c余る数が1個であり、a×12≡(B+N)×6×111,111,111,111 (mod p)の場合は、縦の組の候補は、a余る数12個の組か、その他12個の組に確定しそうです。
⑩ここで(i)に戻ります。BとNにどのような整数を入れれば、⑨におけるpが存在するのでしょうか。
実はB=0、N=1としてOKです。その他の場合なら、リストのすべての数に、
・111,111,111,111を引く
・どの桁もqで割り切れる時、qで割る
・111,111,111,111から引く
の操作を適当な順番で何度か施すことで、B=0、N=1の場合と一致させることができます。
⑪あとはpを見つけるだけ。a余る数が12個あるなら、リストのある2数の差24C2個中、pで割り切れる数は12C2個で、だいたい4分の1くらい。b余る数についても考えるとだいたい半分くらいはpで割り切れるはずです。
互除法も使えば、人力でもpを見つけられそうです。
しかし、9以外で割り切れる気配がありません。
(ii)でもっと複雑な場合を考えなければならなかったのでしょうか？これは手詰まりなのでしょうか......？
⑫ここからが謎解きパートです。まだ使っていない情報があります。「B」と「N」です。より美しそうな、「0」「1」などを用いたナンバースケルトンではなく、わざわざ存在しない単語を用いてまでしてスケルトンとして出題されたわけなので、何らかの意味を持っていそうです。
ここで閃きます。Binary Number(2進数)です。
⑬あとは簡単で、よくあるハバネロ程度の難易度です。リストを2進数に直し、適当な2数の差をとって素因数を調べると、17で割り切れることが多いことが分かります。実際例えばB=0、N=1のとき、17で割った余りが
16......13個
12......9個
0......2個
となり、16×12≡6×(2^12-1) (mod 17)となっています(2^12は2の12乗)。
縦12個の組と、残りの横12個の組がどうなるか考えます。余りが0の数が各組に1個ずつ入ったとすると、余りが12の数が奇数個(9個)あるため、組の和がmod17で等しくなることはありえません、よって、余りが0の数2個、余りが12の数9個はすべて同じ組に入ることが分かります。
残りの1個の数も、各組どの桁についても、0が6個、1が6個となることからすぐに分かります。組分けが終わりました。
⑭ここから解き進めるのもなかなかに大変ですが、よく見ると、似た数が同じ組に入っていることがあることが分かります。「NNNBBBBNBBNN」と「NNNNBBBNBBNB」など、2箇所しか違わないペアが2ペアあります。逆に、これらのペアが入っていない方の組については、上から1桁目=5桁目、9桁目=12桁目となっていない数がそれぞれ2個しかありません。つまりペアは「1列目と5列目」もしくは「9列目と12列目」に入ることが分かります。
⑮これ以降はペンシルパズルっぽく解けます。
3. 一般化
まとめると、
『リストを2進数に直すと17で割った余りが0...2個、12...9個、16...13個なので、縦12個、横12個の組が確定する。ハミング距離が2であるペアが2ペアある組があり、それが入る位置から決めていく。』
というパズルでした。
ここからは考察の時間です。
(ii)についてはどうしようもないです。2. の⑨にある一般化からちょっと派生したくらいの内容でないと、せっかくいいpを取れても人間には手に負えられません。
問題は(i)です。今回は2進数が正解だったわけですが、別に何進数でも構わないわけです。
究極には、別にhoge進数みたいな規則が何もなくてもよく、1以上12以下の整数nについて2値関数fn:{B, N}→{0, ±1, ±2...}を1つずつ定めさえすればよいのです(なんなら値域が整数でなくてもよいかも)。
このとき、各単語について、例えば「NNNBBBBNBBNN」は
f1(N)+f2(N)+f3(N)+f4(B)+... ・・・(※)
という整数に置き換えられます。
縦または横の組に含まれる12個の単語について、どの桁にもBが6個、Nが6個現れるので、12個の(※)の和は
6×{f1(N)+f1(B)+f2(N)+f2(B)+f3(N)+f3(B)+...}
となり、これはfnにのみ依存する(組にどの単語が含まれるかには依存しない)整数となります。よって、このfnを元に(ii)の議論をすすめることができるわけです。
例えば先程の想定解は2進数なのでfnはn桁目の値、つまりx=0, 1で
fn(x)={2^(12-n)}×x
となっていました。上で10進数についても触れましたが、それは
fn(x)={10^(12-n)}×x
のxに、BあるいはNに割り当てた数字を代入する場合と考えられます。
4. 計算複雑性
計算量の視点でこのパズルについて検討してみます。
n×nのBNスケルトン(BNスケルトンとは上述のような形式のスケルトンであって、fnが一般の場合、つまり十分難しいものを指すこととする)について、全探索で解く場合2n!時間、もう少し賢く解く場合、例えば横1行目、縦1列目、横2列目......と決めていくと少し楽になるかもしれませんがそれでも指数時間以上、そして解が与えられればそれが条件を満たしているかどうかの確認はO(n^2)(つまりn×n回の定数倍回のステップ以内で確認できる、という意味)で終わります(多分)。
ここまでは通常のパズルと同じです。クラスNPっていうやつです。
ここからが面白く、fnとpの情報も与えられれば、(ii)が単純ならば、このパズルが唯一解であることのチェックまで多項式時間で出来てしまう、ということがBNスケルトンの特徴です。唯一解性の確認まで多項式時間で行えるようなパズルは他にはないと思います。(ただし一般のスケルトンで多項式時間というわけではないですが。)
Column Dance？(竹谷さんによるルール和訳 )確かに同じ作為で問題を作れそうですが、同じ作為なのでノーカウント。
ここで一旦休憩です。
5. ハバネロ三部作のポリシー
私にとってハバネロ製作は、パズルの猛者たちとの勝負の舞台。一貫して理詰めパズルで解き手に勝つことを目指して作られてきました。
しかし、仮定(仮置き)を多用し、全通りしらみつぶしに探索される「全探索(全検)」であったり、適当に仮定して運良く正解盤面を当てられてしまう「引き」で解かれてしまうようでは、気合い十分な人に正解されてしまいます。たとえ難しい理詰めを仕込んでいたとしても、理詰め 'は' 難しいパズルどまり、負けてしまいます。
そのために、いかにして全検erを封じ込めるか。その結論が、「シンプルループTapaトーラスロジック」「嘘つきナンバーリンク」、そして今回のスケルトンです。まだ解いていない(かつ忙しくない)方は、以下を読む前にリンク先から解いてみてください。
要は強い制約を持つ大域手筋を仕込んでみたり、問題の条件に唯一解性を含めてみたりして、理詰めに気づかなければ解けないよう工夫してきました。
そして三作目。もともと全探索以外の解き方がなかったスケルトンに大域手筋を練り込んだ結果、今回も仮定での解法は完全に潰せたといってよいでしょう。
実は三作ともアイデアから先に生まれており、今作も「ナンスケに0と1しか出てこなくて、しかも全部桁数が同じだったらヤバそう」という発案から生まれています。盤面をシンプルに正方形にしようと決め、せっかくだから0も1も同じ個数にしようと決め、これにどんな大域手筋が働いているか考えたところ、⑥を見つけ、10進数では人間には計算が大変そうなので2進数にした、という、ほぼ想定解と同じ向きの流れで作問されています。
6. さいきょうのパズルは何か？
さて休憩も終わり、あとはまとめるだけ。
理詰めパズルで解き手に勝つためにハバネロを作ってきましたが、その中でもスケルトンは異質で、自重した上でのあの難易度でした。
もしスケルトンで自重しなければ、上述の通り、どれだけでも難しいパズルを作れたことでしょう。
というわけで「さいきょうのりづめパズル」の答えはBNスケルトン!!終わり!!
というわけにもいかず。
BNスケルトンは本当に「理詰め」なのでしょうか。
fnは天下り的に見つけるしかないので、ある意味「引く」しかないです。では「引き」のパズルでしょうか。
そもそも「理詰め」とはなんでしょうか。「引き」とはなんでしょうか。「全探索」とはなんでしょうか。
とりあえず定義してみました。
a. ある1ステップについて
「仮定」・・・場合分けで解き進めること。
「手筋」・・・場合分けよりも効率良く解き進めること。今回は、前例のない初出のものであっても、仮定よりも効率が良ければ手筋とみなすことにします。
いずれにしても理論などが手筋なのか仮定なのかみたいな議論はここでは省略します。
b. 全体について
「広義理詰め」・・・唯一解を確認できた状態で正解すること。
広義理詰めのネーミングのモチベーションとしては、『仮定もロジックであることには変わらない』という気持ち。
「理詰め」・・・主に手筋を使って解き、唯一解を確認した状態で正解すること。
「全探索(全検)」・・・主に仮定を使って解き、唯一解を確認した状態で正解すること。
目解きレベルの背理法は仮定としてカウントしない、などさまざまな会派がありますがこれも省略します。
「引き」・・・唯一解を確認できていない状態で正解すること。
全探索の途中で正解し、探索を放棄した場合が引き、放棄しなければ、あるいは最後まで引けなければ全探索となるので、そういう意味では引きと全探索は似た手法だが、ハニーアイランドなど最適化系パズルでは全通り試すわけではなく解に近そうな盤面のみ探索していくことが多く、これらは引きではあるが全探索ではない。
つまるところ、ハバネロ三部作は「全探索」「引き」が絶望的で「理詰め」が難しいパズル、ということです。
そして問題は、BNスケルトンは理詰めパズルかということでしたが、定義より問題なく広義理詰めパズルであるとは言えるでしょう。
ただ、全探索は無理ということだったので、狭義理詰めパズル、つまり手筋を使って解くパズルということになりますが、これはなぜかしっくりこない。
恐らくそのもやもやの発生源になるのは手筋の発見難易度です。BNスケルトンにおける手筋とはfnを用いてリストを数字に変換することですが、「仮定」より効率よく解くための手筋であったはずなのに、実際に手筋を使おうとすると仮定よりも多く場合分けをしなければならない可能性が高いというねじれの状態がもやもやするのだと思います。
というわけで分類を増やしてみます。
「理詰め」・・・全探索よりも種類数が少ない手筋を用いて解き、唯一解を確認できた状態で正解すること。
「エスパー」・・・全探索よりも種類数が多い手筋を用いて解き、唯一解を確認できた状態で正解すること。
「全探索」・・・主に仮定を使って解き、唯一解を確認した状態で正解すること。
「引き」・・・唯一解を確認できていない状態で正解すること。または、これにエスパーを加えたもの。
うーん、エスパーも理詰めとみなした方が良かった気もする。
7. 6の答え
「最凶の理詰めパズル」、答えの1つは、エスパーを理詰めに含めるのであれば「エスパーしたら解けるパズル」、含めない場合は「限りなくエスパーに近い理詰めパズル」ではないでしょうか。
8. 展開
話題に事欠きません。
8.1 ソルバーに解けない問題
semiexpさんがこのようなツイートをしていました。もしBNスケルトンをn=30くらいで作れれば、ソルバーに解けない闇パズルを自動生成できそうですが、残念ながらそうもいかず。元は10×10だったんですが計算機を回した結果条件を満たすものがなく、12×12で探し始めたものの探索量が組み合わせ爆発を起こし、探索時間を定数倍早くするコードに書き直しつづけてやっと2日かけて見つけたのがあのスケルトンです。多分これの定数倍くらいしか早くならないはずなので、このままではおそらく不可能かと思われます。
「このままでは」というのは、Column Danceでならおそらくソルバーに解けない闇を自動生成するソルバーを作れそう、ということです。n=120、p=31、各列に1が4つづつになるようにし、fをfi(0)=0、f1(1)+・・・+fn(1)≡0(modp)と定め、正解となる列についてはfの和がpの倍数、正解に含まれない列についてはfの和がpで割って1余るようにすればOKのはず。何ならこの手法で、人間に解けないパズルを人間が生成するだけではなく、ソルバーに解けないパズルを人間が生成できるかもしれません。
と思ったけど、SATソルバーは最強なのでそんなことないかもしれない。それでもソルバーに解けない闇Column Danceを自動生成することは可能なはずです。
8.2 プログラム使用について
作り手と解き手の関係、みたいなものが話題になることがあります。
私としては、作り手としても解き手としても何でもありのスタンスですが、今は私の気持ちはどうでもよくて、今回言いたかったのは、作り手がソルバーあるいは一般にプログラムをつかうと解き手と対等でなくなるとか、作り手は唯一解性を担保しなければならないのでプログラム使用は妥当なハンデであるとか、そういう話に一石が投じられたのでは、ということです。というのも、8.1が正しければ、作り手はプログラムを使うまでもなく、人間に解けないパズルを生成できることが証明されたことになるからです(。一応この例以前から、間違い探しみたいな例はありましたが)。こうなると作り手は解き手にあわせて難易度等を調整するのが無難な気がします。ただし、これは一般のパズルにおける話で、パズル種を制限した上で議論すればこの限りではありません。
ついでに。一口にプログラムと言っても指す内容は様々です。こういうときに大事になるのは系統分類ですが、わんどさんがまとめたこの記事が秀逸なので参照させていただきます。例えばBNスケルトンは「人間+プログラムによる作問」の「趣向を考え、プログラムの補助によりパズルを作成する」に分類され、また出題者と解答者の対等さという点では、「検証に利用」の項の、「人による解きチェックを行っていない」使い方が問題になりやすいかと思われます。
8.3 パズルと謎
何かと縁が深いパズル界隈と謎界隈。作り手解き手の構造や、使ってる脳みそが似ていることなどが理由なのでしょうか。この節ではパズルと謎が融合したものについて取り扱います。
よくあるものだと、謎解きの最中にパズルが現れる、というものです。ピースを組み合わせると地図が完成したり、一筆書きになるようにスタートからゴールまで進む際に拾った文字が文章になっていたり。
一方でパズルのフィールドに謎っぽいものが表れることもあります。例えばインストラクションレスです。ルール文がないパズルがあり、そのルールを推測して解くというパズルですが、その推測パートがかなり謎解きに近いです。他にも、リストの単語数が明らかに足りないスケルトンなど、そのままではうまく解けない謎解き要素のあるパズルもまあまああります。
パズルらしさ、謎解きらしさついては諸説ありますが、今回は以下のように定義してみます。
パズルのルール・・・明確ではっきりしている
謎解きのルール・・・曖昧な点がある(そこをはっきりさせていくのが解き手の目標)
パズルの解き方・・・論理的に考えていく
謎解きの解き方・・・ひらめく
この定義の上では、前者の例は「ルール、解き方ともにパズル」、後者や、前者でルールに隙がある場合は「ルールは謎解き、解き方はパズル」が多いかと思います(私は謎解きはパズル以上に詳しくないので、このあたり謎解きクラスタから異論が出そうですが。)今回は「ルールはパズル、解き方は謎解き」という例でした。
エスパーが必要なパズルを解けるようにするには何かしらのヒントが必要で、今回はそれを謎っぽく「B」「N」で表したわけです。かなりめずらしい例かと思います(私が知らないだけかも(この節、保険をかけてばっかりですみません))。他の例としては、bayさん作のこのパズルなどもこの分類かもしれません。こちらは理詰めにめっぽう強いパズラーならパズル的にも解けます。
8.4 暗号
暗号理論とも関係がありそうです。つまり、製作者を発信者、唯一解チェック者(fnが何か知らされている)を受信者、解き手を盗聴者としたとき、オラクルfnを共通鍵とした暗号みたいな、なんかそんな感じの雰囲気をちょっとだけ感じたり。こちらも素人なのでよくわかりませんが。
8.5 スケルトンとは？ (CV. 寺田 心さん)
「スケルトンなのに骨組みになってねーじゃん！」
ースケルトンの条件に白マス2×2禁はないです。また、単語を23文字にすれば同値な問題を骨組み盤面に直せますが、私は12×12の方がbetterな気がしています。
「スケルトンなのに単語じゃねーじゃん！」
ーごめんなさい。
8.6 2章⑨について
「一般に、・・・」以後の部分、ちょっとだけ制約があったりするが、頑張ればなんとかできる、はず。
8.7 6章について
パズル界の話題は多分そんなに多くはないので、「理詰め」の定義については頻繁に話され、先月も盛んに議論されました。持論としては、線引きの方法以外にも、理詰めという単語自体実は文脈依存で、これが議論がまとまりにくい理由かもしれないと思ったりしてます。以下文脈を色々考えてみますが、私の気持ちは便宜上述べただけで、要は文脈依存性について主張したいだけです。
まず6章ですが、あるパズルがどういうタイプなのか考えたときに「理詰め」か「試行錯誤(全検とか引きとか)」かという軸がありがちだが、、、という文脈を想定してます。
他には、ある1ステップについてそれが理詰めか仮定か、みたいな文脈では、a. で手筋と呼んでいるものが「理詰め」で、あくまで列挙済みのテクニックのみを「手筋」と呼ぶと思ってます。先読み、目解きについては6章では理詰めの範疇としましたが、この文脈では仮定に分類したいです。理詰めと仮定で分けない場合には6章と同じで、それこそ目解き可能レベルであれば仮定かつ理詰めとも呼ぶこともあるかと思います。
他にも「理詰めで解ける」という文など、「理を詰める」という行為は人間が行うものであるということを意識した文脈では、
「理詰め」・・・人間が処理できるレベルの手筋を用いて解き、唯一解を確認できた状態で正解すること。
「鑑賞用」・・・人間が処理できないレベルの手筋を用いて解き、唯一解を確認できた状態で正解すること。またはこれに、人間が処理できないレベルの全探索を加えたもの。
とかにするとしっくりくるかも。
8.8 7章について
答えの1つ、というのは、例えばfffさんの記事によると『任意の計算可能関数をスリリンとして表現できそう』ということですので、「難しい数学の問題を計算可能関数にしたものをスリリンにしたもの」なども、最凶のパズルの候補になりうる、ということです。(あってる?)
こういう意味では、エスパーしたら解けるパズルは今回が初出だったわけではないのですが、それをこのサイズの既存のパズルで表現できたのは新規性があると思っています。
8.9 8.3などについて
8.3まで、今回のスケルトンは謎解きすれば解けるという論調でここまで通してきましたが、かなり怪しいと自認はしています。想定解の謎解きパートは2.⑫でこれ自体導線が2バイトしかなく難しいですが、あまり考察をしていない段階、例えば2.⑥の内容を踏まえずにBinary Numberを思いつくのはさらに難しい一方、十分な考察を経た段階、つまり話の都合上後回しにした3章を知っている状況でBinary Numberを思いつくのも同様にさらに難しいです。まぁハバネロなのでこの辺の理不尽な難しさは許してください、何でもしm
8.10 なにかクリティカルな間違いがあれば私の方までお知らせください。
こんだけ書いておいて「BNスケルトンが実は多項式時間で解けました」とか報告されたらどうしよ。
8.11 「数独」「ペンシルパズル」「スリザーリンク」「ナンバーリンク」はニコリの登録商標です。
どういうときにこの文を添えるべきか分かっていない。
8.12 謝辞
ツイートなど引用させていただいた方々、ありがとうございます。
本記事に載せようと思っていた付録パズルの唯一解検証に付き合ってくださったまどれーぬさん、ありがとうございました。そしてパズルが完成しなくてすみませんでした。
9. 最後に
ここまで読んでいただいた方、飛び飛びでもよいので記事に目を通して頂いた方、ありがとうございます。感激で胸がいっぱいです。そしてそれが何かしらの形で皆様にプラスに働いたのであればこちらとしても至極の極みです。これ以上何も望むものはありません。強いて言えば、「いい感じの謎パズル作ってくれー！」とか「新手のエスパー見つけてくれー！」とか、「他のハバネロ2つも解いてくれー」とか、それくらいしかありません。
それではよいクリスマスを。