理詰めをやめたい

本記事はペンシルパズルI Advent Calendar 2021の13日目です。

こんにちは、lilvaです。Twitterパズル歴2年です。本日は13日、13といえばそう、成宮由愛ちゃんの年齢ですね！！……この話は去年したので今年は別の話を。突然ですが「理詰め」をやめたいと思ったので、その経緯を話そうというのが本記事の内容です。

理詰めが何かはよく議論される内容の一つで、人によって様々な考え方があって興味深いです。私は元々「先読みは認めない」と同時に「探索が困難なものでも論理的に正しいならば認める」立場です。歪んでいるような気もしますが、先読みで説明できるなら先読みでなくても説明できるのでは？という考えがあり、そのため先読みは含めない、あるいは逆に仮置き含め全てを認めるということを最近は考えています。

ここ最近の興味は理詰めや手筋にどのようなものがあるか、どういったことができるかを主に考えていることが多いのですが、そもそも理詰めが何か、手筋が何か、その定義が人それぞれで揺らぐと考察する上で困ります。小ループ禁がどのように扱えるかとかチェインやネットがどのような力を持つかとかシンプルループ仮説(オリジナルの用語。シンプルループは市松手筋を単純に利用するだけで解くことができるかという疑問)とかそのうち考えたいと思っていますが、まずは確実で揺らがない足掛かりが欲しい。……よし、「理詰め」やめるか。

ということで要は「理詰め」よりも自分にあった用語を定義し直しまして、まず自分用の考察の道具を作ろうとしました！試行錯誤問は作りません！私はそもそも先読みが苦手なので作れません！

注:頭の中で適当に考えたものを整理が不十分な状態で放出しており、現状とても不完全なものになっています。今後もう少し整理したい……。

1.目的

目的
・明確に定義された、理詰めや手筋にあたる代替用語の構成

それにあたって
・何を定義にするかにはlilvaの判断が入ってしまうが、少なくとも定義自体は人それぞれを最大限回避することを心がける。
・自分の知らないことも多いため、より良い定め方があれば取り入れたい。

加えて考えておく必要のある事
・そもそも理詰めや手筋以前に、(ペンシル)パズルとは何であって、それを解くとはどういうことか。

2.構成

考えたことをそのままつらつらと書いていると分量が多く間に合わないので(そもそもちゃんとまとまってもいない)、今回は結論となる構成方法に絞って書き、そこから続く内容などについてはいつか時間があるときに書こうと思います。

注1:ここからずっと「何言ってんだこいつは……」という内容しかありません。
注2:lilvaは英語ができないので記号の振り方は適当です。

定義１.(盤面要素)
書込の最小単位を盤面要素と呼ぶ。誤解がなければ単に要素と呼ぶ。

数独であれば各マス1~9の729個が該当し、10×10のヤジリンであれば黒マスかどうかの100個とマス間に線を引くかどうかの180個が該当します。ただしヤジリンの表出は白マスでも黒マスでもない状態になるため、あらかじめ盤面外として扱い、盤面要素には含めません。数独の表出は盤面外として扱う以外に、既に書き込まれた要素として扱っても良い(し、その方が対称性が高く議論しやすそう。)

一般にパズルは多値ですが、まずは二値として扱うことで同じマスに複数の書き込みがされないという暗黙の了解を陽に制約に加えて扱えるようにします。これはチェインなどでより統一的な扱いが出来そうと考えたためですが、多値の方が良さそうな場面もそのうち考察するかもしれません。

定義２.(制約)
盤面要素が満たすべき条件を制約と呼ぶ。

基本的にはソルバーの話題で出てくるようなSATやCSPのようなものをイメージしています(よくわかっていないので立ち入りません)。一つ約束事としてルール文のような複数の制約を一般にまとめた形ではなく要素間の条件として具体的に書き表されていることを要請します。

数独であれば(表出を既に書き込まれた盤面要素と考えて)、行列ブロックで1から9が一つずつ入るという条件とマスに1から9がいずれか一つ入るという条件を具体的に書き直したもの、ヤジリンでは黒隣接禁、線の分岐交差端点禁、白マスには線が通る、小ループ禁、矢印の制約を全て具体的に書き直したものになります。

ルール文をどのように書き換えるかというのはソルバーの構築に非常に似ていると思われます。具体的なやり方、形についてはそれだけで一本記事が書けそうなのでここでは省略します。ソルバー構築の場合処理が速くなるように適切に変形して記述する必要もありますが、手筋などの考察においてはそういった変形もまた考察の対象にしたく、基本的にはルール文をそのまま訳した形に近いものを考えたいです。

また、ここで定める制約とはパズルを解く途中経過で得られる情報も含みます。確定した盤面要素や、途中で得られる2択3択などの情報も制約の一部として扱うことで制約自体がパズルの進捗を表すことになります。

定義3.(論理構造)
盤面要素の集合$${X}$$とその上の制約の集合$${R}$$の組$${(X,R)}$$を論理構造と呼ぶ。誤解がなければ単に構造と呼ぶ。

要はパズルの構造は盤面とルールが分かれば決まっているだろうという気持ちを込めた定義です。定義に入れた通り制約の対象となる要素は必ず集合に含まれているとします。逆は無くても問題はありませんが、制約のない要素があると複数解なので、考える対象は制約の集合とそれら制約の対象となる要素集合の組としてよさそうです。この意味で制約から構造を構成できます。制約集合$${R}$$の対象となる要素集合を$${D(R)}$$とでも書くことにします。

ここで定めた構造とはパズルがどう定まっているかを表すものであると同時にパズルを解く上での進捗を表すものにもなっています。そして以下のようにパズルを解き進めることを定義します。

定義4.(論理推論)
盤面要素集合$${X}$$とその上の制約集合$${R,S}$$について、$${R}$$が成り立つとき$${S}$$も成り立つならば、構造$${(X,R)}$$から$${(X,R \cup S)}$$を得るこの操作を(論理)推論と呼ぶ。$${(X,R)\to (X,R \cup S)}$$とでも書くことにする。

成り立つとかどうこうは制約の自然なイメージにとりあえず任せます。構造が解く過程の状態を表すので、そこから論理的に正しい別の構造を得ることはいわゆる一番広い意味での、論理的に正しいならば全て認める立場としての「理詰め」にあたるものになっているのではないでしょうか。

定義5.(唯一解)
構造$${(X,R)}$$の任意の盤面要素$${x\in X}$$に対応するリテラル$${L_x,\neg L_x}$$(=$${L_x}$$の否定)について、$${(X,R)\to (X,R\cup L_x)}$$と$${(X,R)\to (X,R\cup\neg L_x)}$$のいずれか一方が推論であるとき、$${(X,R)}$$は唯一解であるという。ある盤面要素$${x\in X}$$について上の両方が推論であるとき、破綻しているという。どちらでもないとき、複数解であるという。

全ての要素がどうなるかが確定するということを書いただけであり、多分自然だと思います。破綻については暗に排中律があるので一つについて$${L_x}$$と$${\neg L_x}$$が成立するならば矛盾してありとあらゆる全てが成り立ってしまいますが……。

ここまで、これはこれで「解き進めるということ」の定義の一つとしてはいいのですが流石に理詰めというには無理がありそうです。以下の例は人間には真似できそうもありません。

・神の解法
$${(X,R)}$$を唯一解とする。各盤面要素$${x\in X}$$に対応する、推論となる方のリテラルを$${\~{L_x}}$$と書く。このとき$${(X,R)\to (X,R\cup \bigcup_{x \in X}\~{L_x})}$$は推論。

こう手をかざしたら答えが全て浮かび上がるようなイメージ。だがこの定義の下では唯一解なら全マス同時に埋めようが好きな順番で埋めようが論理的に正しいのでOK。

これが人間的に不可能である理由の一つとして、初めに定めた制約の集合は人間が把握して同時に利用できる分量を大幅に超えていることが挙げられます。実際にパズルを解くときには、盤面全体のありとあらゆるルールを同時に取り扱うのではなく基本的には局所的な様子のみを見ながら進めていくため、その進め方を表すことができればより普段の「理詰め」や「手筋」に近いものになると考えました。

定義6.(部分(論理)構造/部分(論理)推論)
構造$${(X,R)}$$に対し、$${Y\subset X,S\subset R}$$を満たす構造$${(Y,S)}$$を$${(X,R)}$$の部分(論理)構造と呼ぶ。さらに$${Y}$$上の制約$${T}$$で$${(Y,S)\to (Y,S\cup T)}$$が推論であるとき、$${(X,R)\to (X,R\cup T)}$$も推論である。これを$${(X,R)}$$の部分構造$${(Y,S)}$$における部分(論理)推論と呼ぶ。

このように定めれば解く上で盤面全体に毎回注目しなくとも、その一部分を見ながら解いていく様子が表現できそうです。

非常に簡単な部分推論の例:
$${(S\vdash T)}$$
$${A,A\to B\vdash B}$$
$${\neg A,A\lor B\vdash B}$$

ここまで基本的なものはなかなか意識されませんが、こういった基本的な操作を見つけ、繰り返し適用しながらパズルを解いていくと考えます。さらにこの部分推論をいわゆる「手筋」に近づけていくために、この部分推論にさらなる評価、比較の基準となる分類を入れていくことを考えます。最後に一つくらい評価基準となりそうなものを挙げて終わります。

定義7.(極小化)
$${r}$$を$${X}$$上の制約とする。推論$${I:(X,R)\to (X,R\cup\{r\})}$$について$${R}$$の部分集合$${S}$$であって、$${J:(D(S\cup\{r\}),S)\to (D(S\cup\{r\}),S\cup\{r\})}$$が推論であり、かつ任意の$${T\subsetneq S}$$について$${(D(T\cup\{r\}),T)\to (D(T\cup\{r\}),T\cup\{r\})}$$が推論でないとき、推論$${J}$$を$${I}$$の極小推論と呼ぶ。

こいつのイメージは要するに「何か決まること$${r}$$について影響を与えない余分な要素や制約を取り除く」です。ただ必ずしも完全に取り除くのが便利とも言えないので難しいところですが……。なお極小化は全く一意ではありません。

まだまだ考えねばならないことは多いですがとりあえずこの辺りで終わります。自分が具体的な考察をする上での最低限の道具は揃ったかな……。

3.で、結局のところ……

そんなこんなで考えたこれらは結局自分で適当に考えて自分で使うためのおもちゃに過ぎませんが、少なくともパズルを解くことについて今後もこういった道具を必要に応じて勝手気ままに作りつつ色々考えてまとめていければと思っています。頑張るぞ〜。