この記事は「ペンシルパズルAI Advent Calendar 2019」2日目の記事です。
こんにちは、SP1といいます。
今回のテーマは「大域手筋」です。
0. イントロダクション
0.0. パズルを解くということ
大域手筋とはなんでしょうか？それを述べるため、まずはペンシルパズルを解くときの過程・思考を考えてみましょう。
たとえば、スリザーリンクを解くとしましょう。最初、ほとんどの人は盤面の数字を眺めて、0 と 3 が並んでいたり、3 と 3 が並んでいたり、そういう場所をみつけては線を引いていくことになるでしょう。これらは「手筋」(＝定石) として認識されていて、すぐにわかる場所として真っ先に線が引かれます。
あるいは、ルールから素直にわかる場所を引いていくことになるでしょう。すなわち、「枝分かれのない一本のわっかを作る」というルールから、線が途切れている場所をちょっとずつ伸ばしていくことになります。
さて、これらをやって進まなくなったとします。ちょっと慣れている人なら偶端手筋、すなわち「閉所にはちょうど偶数本の線が入る」という事実を使って線を引くかもしれません。
はいきました！これです、これこそが大域手筋です。
0.1. 局所手筋と大域手筋
このままだと説明がおおざっぱすぎるので、さっきの例をまとめておきます。
まず「手筋」とは、特定のパズルでよくあるパターン・定石をまとめたものです。
そのうち、盤面のヒントやすでに置かれたものの周りからわかるものを「局所手筋」とよびます。というより、そうよぶことにします。
一方、先ほどの偶端手筋など、盤面の様子全体を眺めて決まるような考え方を「大域手筋」とよぶことにします。
さて、局所手筋は、個々のパズルでバラバラのパターンが出てくることが多いです。スリザーリンクの数字の扱い方を、ましゅとかヤジリンに応用はできないですよね。
一方、大域手筋は複数のパズルで使えることがあります。さっきの偶端手筋は、「盤面に枝分かれのないループを描く」パズルならなんでも使えます。スリザーリンクのほかに、ましゅとかヤジリンでも使えるわけですね。
0.2. 分類
大域手筋を分類するときは、最初にパズルのジャンルで分けておくと見通しがよいです。
ペンシルパズルの分類の仕方はいろいろありますが、ここでは次の 5 つとします：
・数字埋め系
マスに数字 (や文字) を書き込むパズル。ラテン方陣になるものもこれ。
・線引き系
線を引くパズル。これらはさらに、わっか (ループ) につなぐものと、線をつなぐもの (パス) に分かれる。
・塗る系
マスを塗るパズル。単に塗るものもあれば、塗ったマスがひとつながりにすることもある。
・配置系
盤面に物を置くパズル。同じ物を置くこともあれば、別のものを置くこともある。
・分割系
マスを分割するパズル。
0.3 この記事について
この記事は、ペンシルパズルで現れる「大域手筋」と、その考え方をまとめたものです。なお、試行錯誤をする問題については、今回は扱わないのであしからず。
大域手筋の性質上、ペンシルパズルを広く浅く俯瞰することになります。ただし、これを知っておくことで、難しい問題に使えたり、未知のルールの問題に応用したりできるかもしれません。また、問題を作る時に仕込んでおけば、いいスパイスになること間違いなしです。(もちろん、辛すぎるのはよくないけどね。)
以下各章に、大域手筋のテーマと、それぞれのジャンルでの使い方をまとめています。考え方ごとに章立てていますが、逆にジャンルごとに読んでみるのもおもしろいかもしれません。
なお、各節に練習問題をつけています。これは正直に言うと、説明をさぼりました。すいません。とはいえ、ちゃんと練習になったり、考察が深まったりするので、ぜひ考えてみてくださいね。
1. カウンティングと不等式評価
1.0. 概要
いよいよ本題です。まずは大域手筋の華、カウンティングです。やることはその名の通り、わからなかったらとりあえず何かを数えましょう！
ただし、やみくもに数えても何もわからないので、ある程度方針を立てる必要があります。その方針の一つが不等式評価です。
なんか数学チックですが、作戦自体は難しくはありません。たとえば、あるもの X の個数を数えたとき、作戦 A を使って X が 10 個以上とわかり、他の作戦 B を使って X が 10 個以下とわかったとしましょう。すると、X は 10 個と確定します。簡単ですね。
ただし、ここで大事なのは等号成立条件です。これもなんだか数学チックですが、要は作戦 A で X が 10 個以上とわかり、実際 10 個になるのなら、作戦 A について「ちょうど」 10 個になるための制約がかかるということです。作戦 B についても同じです。この制約が、パズルの盤面を埋める際にキーとなることが多いです。
1.1. 数字埋め系
数字埋めのパズルでは、数字の個数のカウンティングや、和で評価の評価ができることがあります。
個数カウンティングで有名なのは、「井桁理論」、別名 X-wing です。
練習1.1.1. 井桁理論を個数カウンティングと思って説明せよ。また議論を拡張するとどうなるか？("Sudoku Franken Fish" で検索しよう)
和の評価は、カックロやキラー数独といった、足し算を使う問題で難問として出てきます。
練習1.1.2. 2017 Sudoku GP Round 2 で出題された Killer Sudoku (キラー数独) を解け。なお問題はここの Competition Puzzles から確認できます。
練習1.1.3. サイズ 5 の魔法陣の四隅の和の最小値が 26 であることを示せ。すなわち、
・四隅の和が 26 になる例を構成せよ。
・四隅の和が 25 以下にならないことを示せ。
(「SATソルバー」なるものを作っていたら、謎の事実が出てきた)
1.2. 線引き系
線を引くパズルで不等式評価が使えることは少ないですが、カウンティングは時として有効です。
特によく出てくるのが、最初の説明でも使った「偶端」です。すなわち、ループを作るパズルにおいて、「閉じた部分に線は偶数本進入する」というものです。これは「ループをどんな分割線で切っても、切れ目がちょうど偶数個出てくる」という事実に基づいています。
練習1.2.1. 偶端を使うスリザーリンク・ましゅ・ヤジリンの問題を作成せよ。
もうひとつ、偶奇を利用するものとして市松塗り分けがありますが、こちらは次の章で詳しく扱います。
あと、長さを使う線引き系では、長さを評価してうまくいく場合があります。Castle Wall なんかでたまに使います。
1.3. 塗る系
塗るパズルでは、カウンティングや不等式評価が使えることは少ない気がします。なんとかしぼり出せば、2*2 禁があれば盤面の塗るマスの個数が評価できたり、ぬりかべでの頂点カウントがあったりするのですが、前者はあまり使えないのでスルーし、後者はのちの章で軽く触れることにします。
練習1.3.1. 上記以外でカウンティングが使える例を考えてみよ、というか教えてください＞＜
1.4 配置系
一方、配置系はカウンティングの宝庫です。
二コリ系で言えば美術館ですが、これは「列に照明が 1 つまでしか入らない」という評価とヒントの相性が良く、それを用いた理詰めを仕込みやすくなっています。
練習1.4.1. これらの問題を解け。(拙作、UTPC2017より)
ナナメの接触禁があると、より強力です。
例としてスターバトルでは、「2*2 のマス目に星は 1 個までしか入らない」という評価ができます。加えて、行・列。領域にちょうど 2 個入るというのも評価に使えます。以前に具体的な手筋のまとめを記事にしたので、そちらも参照ください。
さて上記の 2 種は単一のものを配置していましたが、複数配置でも効力を発揮します。最たる例がバトルシップで、「ナナメの2マスの両方を艦が占有することはない」という評価ができるほか、
・ちょうど 10 隻しかない
・ちょうど 20 マスしかない
・長さ X のものがちょうど Y 隻しかない
といった、いろんな切り取り方で評価が可能です。
具体的な問題は、パズル同人誌「トケタ？」にたくさん載っているので、みなさんぜひ買いましょう。 (ダイレクトな宣伝)
練習1.4.2 アプリ "Chocolate Sweeper" を検索してダウンロードし、いろいろ解いてみよう。 (これも宣伝) (練習と呼べるのこれ？)
1.5. 分割系
マス数をカウントするヒントがあるパズルでは、分割系の問題でもカウンティングが有効です。具体的にはフィルオミノやコンパスといったものでしょうか。
練習 1.5.1. 6*6 のフィルオミノで、1 から 8 すべてがヒントとして表出する問題を作成せよ。
練習 1.5.2. 次のコンパスを解け。(拙作)
2. 偶奇・余り・色塗り
2.0. 概要
余り、とりわけ 2 で割った余りである偶奇に注目するのが、議論のカギとなることも多いです。また市松模様など盤面を色塗りするのも効果的です。色塗りは、二次元版の「余りに注目」とも言えます。
2.1. 数字埋め系
シンプルに数字の余りに注目することが多いです。とくに偶奇を扱った数独は、変種ルールの 1 ジャンルにもなっています。
2 以外で割った余りが使えることもある...かも？サイズ 9 の因子の部屋で 5, 7 の倍数に注目、とかありますよね。
練習2.1.1. 次のリンクにある "Pyramid" を解け。ルールは以下の通り：
・盤面の各マスに 1 から 9 までの数字 1 つを書く。
・横並びの 2 マスに書かれた数の和か差は、その 2 マスの両方の上になっているマスに書かれた数と等しい。(たとえば、3 と 4 の「上」には、1 か 7 が入る。)
・灰色の行では、同じ数字が二度現れない。一方、白色の行では、少なくともある数字が二回以上現れる。
問題は、semifinal-2 の一問目です。
ヒント：偶奇とパスカルの三角形
(ちなみに大域手筋関係ないけど、この他の問題も面白いです。)
2.2. 線引き系
1.2. で言ってた市松模様について。マスを市松模様に塗っておくと、当たり前ですが線は交互に黒・白のマスを通過します。このことからたとえば、ループを描くパズルでは、通過する黒マスと白マスの個数は一致します (あたりまえだけど大事)。さらに、次の定理が成り立ちます：
定理 (白黒差分の原理)
マス目に線を引きループを作る。また、いくつかのマスで出来たある領域 D に注目する。D のマスはすべて線が通過するとし、またマス目を市松模様に黒白で塗ったときに D に含まれる黒マスの個数を B, 白マスの個数を W とする。さらに D の境界で黒マスから線が飛び出る箇所の個数を dB, 白マスから線が飛び出る箇所の個数を dW とする。このとき、2*(B-W) = dB-dW が成り立つ。
ちょっと数学の定理っぽくまとめてみましたが、要するに、「領域の黒白の差を 2 倍にすると、境界の黒白の差になる」ということです。これ、結構使えるっぽいですよ。特に難しいヤジリンの詰め。
練習2.2.1. この定理を証明せよ。
その他、「線を引いたときに折れるマスの個数は列で見ると偶数個」とかもわかります。
練習2.2.2. 7*7のマスの隅のマスから対角の隅まで、すべてのマスを通る線を引く。このとき、直進するマスの個数の最小はいくつか？(昔のジュニア広中杯より) (なにその出典)
2.3. 塗る系
やはりこれも偶奇との相性があまり良くない...
塗る系パズルは、塗るマスのつながりを意識する問題が多く、それで十分パズルとして成立してしまっているからかもしれない...うーむ。
練習2.3.1. 偶奇・余り・色塗りが使える例を考えてみよ、というか教えてください＞＜
2.4. 配置系
テトロミノなどのブロックのつながった形については、色塗りの技法が使えることが多々あります。ただし、配置系の問題としては利用しにくいかも。
2.5. 分割系
というわけでここで扱います。
練習2.5.1. 10*10のマス目を、T 字のテトロミノ 25 個に分割できるか？
練習2.5.2. 10*10のマス目を、L 字のテトロミノ 25 個に分割できるか？
練習2.5.3. 次の四角に切れを解け。(拙作、ハバネロとして公開)
3. マスを見ろ！
3.0. 概要
大域手筋とよべるか怪しいですが、よく出てくる考え方なので、一応触れておきます。
通常、何かしらのヒントがあるとその周りから決まっていきますが、逆にヒントのない場所の様子から決まることもあります。
3.1. 数字埋め系
数独の「マスミ」(naked single) が最たる例でしょう。数独でなくとも、よく使います。
また「全表出系」のルールだと、ヒントがないことに注目することがあります。全表出系とは、「条件を満たす場所すべてにヒントが置いてある」タイプのパズルで、Kropkiなんかがそうです。
練習3.1.1. 次の「黒pki」を解いてみよう。
3.2. 線引き系
全部のマスを通る問題では、隅の様子が自動的に決まることが多いです。まあそれだけでは何も進展がないことが多いですが...
ヤジリンでは、ヒントマスがあるだけで白マスが確定するということがありました。詳細は次の「出口の手筋」を参照ください。
3.3. 塗る系
ぬりかべでは、ヒントのないマスに向かって白マスが伸びる、ということが起きます。海外の作品でよく見られる印象ですね (国内のだとこの手筋が制限されているかも)。
ぬりみさきは、二コリ系では珍しく全表出系のルールです。そのためヒントの薄い場所も面白いように決まっていくことがあります。楽しいよ！みんなやろう！
練習3.3.1. ぬりみさきガチャ、やろう！
3.4. 配置系
配置系は配置してナンボなため、何もないところから突然何かが生まれることはあまりないです......別の考え方を使わない限りは。
3.5. 分割系
これも塗る系と同様、ヒントのないマスから制約が生まれることがあり、フィルオミノや天体ショーがその例です。特に海外産の天体ショーでよく見かけますね。
4. チェインと「いずれにしても理論」
4.0. 概要
チェインについては以前まとめた記事がありますのでこちらを参考にしてください。
二択が続くときは、仮定せずともチェインを見つけて理詰めの範疇で倒しきれることもあります。また「二択を考え、いずれにしてもこのマスはこう」みたいな議論もできることがありますが、これも高度なチェインと言えます。
ここで、1 章の評価との関連を書いておきます。
またも例として、あるもの X の個数が作戦 A で 9 個以上とわかり、作戦 B で 10 個以下とわかったとします。すると X の個数は 9 個か 10 個になります。ここで X が 9 個とすれば作戦 A の等号成立条件が成り立つし、X が 10 個とすれば作戦 B の等号成立条件が成り立ちます。こんなタイプの「いずれにせよ」もありえますね。
4.1. 数字埋め系
とくに数独について取り上げたのが去年の (裏) 記事でした。
練習4.1.1. 数独における "Finned Fish" について調べてみよう。
4.2. 線引き系
線引き系で特徴的なものはなさそうです。「いずれにしても」はたまに使いますが。「線を引くか引かないか」で二択が連鎖する、というのはできなくはなさそうですが、具体的に実装された問題は記憶にないですね... 見てみたいな。
4.3. 塗る系
上で挙げたチェインの例で、Tapa の局所的な場所がチェインになっている、というのを紹介していました。
ところで、これ長さ3のchainだったんですね。 https://t.co/fFRqYRPpx0
— SP1 (@SP1_winter) 2019年11月3日
その他、最新号のパズル同人誌「トケタ？」では、このチェインを意識する追加ルールの乗った Tapa が扱われています。みんな、買おう！(また宣伝)
その他、ぬりみさきではマスのペアを利用したチェインが仕組めます。くわしくは、さきほど挙げた手筋集を参考にしてください。
練習4.3.1. 手筋集を読み、ぬりみさきのチェインで長さが奇数のものを見つけよ。ところで、系統的に分類できないかなぁ...
4.4. 配置系
「配置するかしないか」の二択が連鎖しがちで、マインスイーパーや美術館でよく見られます。スターバトルなんかもたまに使えますね。
「いずれにしても」では、美術館で数独のようなフィンが使えるときがあります。
練習4.4.1. どうぞ。たのしいよ！
いや本当に、何なのですかねこれ?難度はLv.5(理詰め)。上級手筋フル活用な上に、大きくてどこから手を付けていいものやら。 #デレマスパズル部 pic.twitter.com/gs5Ugiimff
— あーく (@ark184) 2019年6月28日
4.5. 分割系
これも線引き系と同様ですね。「線を引くか引かないか」の二択の連鎖だと 使えるかも...と考えてたら、四角に切れで二択を繰り返す問題があったのを思い出しました (ニコリのスーパージャイアントだったかなぁ)。どちらかといえば配置系の考え方なのかもしれませんが。
5. 双対盤面・内外
5.0 概要
盤面を「双対変換」して見通しをよくする、という作戦もたまにあります。ここで「双対」とは、盤面を平面グラフで見た時の双対グラフをさします。
グラフ理論を知らない人にはさっぱりだと思うので、そういう人はざっくりと「盤面のマスではなく頂点に注目する」と思っておけば OK です。
なお個人的な印象では、新たな手筋がというより、見通しが良くなる面が大きいかなと思っています。
5.1. 数字埋め系
図形的な操作のため、数字埋めで使えることはあんまりなさそうです。
5.2. 線引き系
線を引く系、とくにループ系で使えることがあります。「頂点に注目」というのはすなわち「ループの内外に注目する」ということです。
たとえばスリザーリンクは、次のようにルールを言い換えられます：
・正方形のいくつかを塗ります。
・塗ったマスはひとつながりになります
・塗らなかったマスは外周に接続します。より正確には、盤面の外周を塗らなかったマスとみなしたとき、塗らなかったマスはひとつながりになります。
・数字は、上下左右について自分と違う色のマスの個数を表します。
スリザーリンクを普通に解く分には、この言い換えが有効なことはほとんどないですが、変種のルールでたまーに使えることがあります。
他にはバッグなどがあります。もともとバッグはニコリで紹介されたときループのパズルでしたが、ループの内外を決めるパズルとも言えます。数字のヒントはループの内側なので、こう見た方が自然ともいえますね。なお、海外では Cave の名で知られており、人気の高いパズルになっています。
(ところで、ジャンルが Division になっているけどほんまか？Shading だと思うけど...)
練習5.2.1. 次のパズル "Dutch Loop" を解け。ルールはリンク参照。
というわけで作ったDutch Loopです。
— SP1 (@SP1_winter) 2018年7月4日
ルール：全マス通過する1本のループを引く。白丸では直進し、黒丸では曲がる。 pic.twitter.com/97stNnv35E
5.3. 塗る系
塗る系はその逆で、双対変換により線を引くパズルに変わります。要は黒マスと白マスの境界を見てるわけですね。
しろまるくろまるでの双対の利用は、かなり革命的です。
ちなみに「2*2禁」は双対においては「その頂点を分割線が通る」と言い換えられます。
このほかに何か使えるパズルがあればいいのになぁ。ぬりみさき？まさかね...
(最近、六角形盤面のしろまるくろまるが研究されてるとか。続報が気になる。)
練習5.3.1 しろまるくろまるにおいて、「丸の個数の差」と「外周の色の差」について考察せよ。ヒント：ピックの定理
5.4. 配置系
配置系、とくにナナメ接触禁の問題では、「頂点注目」が使える場合があります。というのも、ナナメ接触禁だと「その頂点を占有する物体は 1 個まで」という評価ができるためです。これにより、頂点をカウンティング＆不等式評価してなにかが言えることがあります。
次は、その言い換えが成功した例です。
配置系の問題を分割系に落とし込んだあと、色塗りを使って候補を絞って解く、という紹介した大域手筋をふんだんに使った問題でした。作意がどうだったかは知らないですが...
ちなみに頂点カウントは、 (パス系ですが) スネークの問題でもごくまれに使えたりします。これもナナメ接触禁があるためですね。
5.5. 分割系
逆に分割系を配置系に変換するのはあまり見たことがないすかね。ただし、分割線の交わり方に注目するパズルはなくはないです。手筋としてはまだ未開拓ですかね。
6. 終わりに
以上、いろんな考え方をまとめてみました。有名なものをそれなりに挙げたつもりですが、他に何かありましたらぜひ教えてください。
パズル好きがペンシルパズルを解くのは、ルールに沿って盤面を埋めていき、途中難所も乗り越えながら、最終的に埋めあがったときの快感を味わうためではないでしょうか。また、難しい問題であればあるほど、得られる快感は大きくなるでしょう。
そんな楽しさの中にもいろいろ種類があります。手筋をスムーズに使っていく爽快感とか、試行錯誤してやっとの思いでたどり着いたときの達成感とか。そんな中で、自分が一番大切にしているのが、「ぱっと見手がかりのない問題が、ちょっとした論理を使うことで道が拓かれるときの、パッとひらめく感覚」です。この世界が開けたような感覚は、何事にも代えがたいと考えています。
この記事が、その快感を得るためのサポートになってくれれば幸いです。さらに作る側にも、もっと広まればいいなぁなんて思っています。
なお今回挙げた以外にも、まだまだ別の「大域的な」考え方がありえます。未知のパズル・未知の理詰めが生まれる可能性も十分にあるでしょう！まだ見ぬ解き味に出会えることを祈って...... ここまで読んでいただきありがとうございました。
7. おまけ
ここまで新作のパズルがなかったので、おまけに最近作ったパズルを置いておきます。
バトルシップです。一応ルールはこちら：
・盤面に与えられた「艦」をすべて置きます。
・異なる「艦」はタテヨコナナメに接触しません。
・盤面外の数字は、その列で「艦」が入るマスの個数を表します。
リンクはこちら：
ぜひ解いてみてね～
