2013年8月31日土曜日

Conceptis「最も難しい加算パズル」を解いてみた(2)

Conceptis「最も難しい加算パズル」を解いてみた(1) の続きです。
現在の状況はこんな感じ。
















 
(3)
右下からつないで中央へ。
5マス17の6が確定しているので、残りは1235。
埋めていくとA、Bの候補で 【最大最小の手筋】がまた発生して、A=2、B=4に確定。
7マス42との交差から、左下の4マス10まで埋めていけます



さてC~Eのマスに注目。
Cは4マス10で最大4、Dは5マス15で最大5、Eは2マス3で最大2
したがってC~Eの合計は最大11。ヨコの残り3マスの合計最大24。
これでやっと6マス35なので、まさにこのように、C~Eが決まります(*1)

【最大最小の手筋】の大がかりなパターンです。実は初手からいきなり埋められます。初めて見ると手品みたいですが、慣れると普通に見つかるようになります。


FとGの候補が共に「23」になりました。【ペアの手筋】成立です。
常に一方が2でもう一方が3の関係になりますから、同じヨコ列にもう2と3は入りません。よってH=4
さらにI=3となるので、JとKで12のペアが成立してG=3
一帯の1~3が一斉に決まります。
このパズルの面白いところですね


【ペアの手筋】は3つのマスでも成立(たとえば同じ列で候補123の3マスなど)して、その場合は【トリプルの手筋】と呼びます

こんなところで盤面下は一旦終了。候補が絞られてきたマスも多いので、書き込んでおくのもよいでしょうか


(4)
次は上から埋めていく番ですが、その前に手筋の紹介を兼ねて、小さく埋められる場所を紹介します。

Aのマスに注目。
このマスの候補は6789ですが、仮に7~9のどれかと仮定すると、ヨコ列で789の【トリプル】になります。すると残り3マスの和は29-24=5なので、これを満たす組み合わせはありません(3マスの和の範囲は6~24)。
よってA=6。

このように、ペアやトリプルが発生すると矛盾してしまうことから、そのマスの候補を減らすことのできる場面があります。この手筋を、 【アンチトリプルの手筋】と呼ぶことにします(*2)





タテ24に注目。
6マス24の分解を考えてみると、123459、123468、123567
の3通りしかありません。したがってこれらの共通項である123は、必ず存在します(*3)。
既に決まっている2を除き、13の行き先を探すと、ヨコ列との交差から、B=1、C=3が決定します。

このように、和の分解が完全には決定しなくても、「ある数字がこの列に必ず存在する」という情報を元に、その数字を配置できることがあります。これを【存在証明の手筋】と呼ぶことにします

2通り以上の和のパターンを調べるのは面倒に思われるかもしれませんが、実際にはこのようにすべてを書き出す必要はありません。

仮に6マスで1が存在しないとするなら、最小の和は234567=27>24。よって1が存在。
仮に6マスで3が存在しないとするなら、最小の和は124567=25>24。よって3が存在。
仮に6マスで4が存在しないとするなら、最小の和は123567=24。よって4は存在しないかもしれない。
これより上は調べても無駄。

このように不等式で評価して、順に絞り込みます。
より高度なケースでは、列内の既に決まった数字(上の盤面における6のような)を考慮に入れることでさらに絞り込める場合があります(*4)。







(*1) 前回と若干表現は違いますが、本質的な考え方は同じです
(*2) この手筋については特に決まった名前がないので、ここで名前をつけました。このパズルには、決まった名前のつけられていない手筋が多数あります
(*3) 6の存在から、123459も除外できます。が、現時点ではあまり重要ではありません
(*4) なお、そんな場所をどうやって見つけるのだという意見もあろうかと思いますが、あると思えば、意外に見つかるのです。このケースで言えば、6マス22は分解が一通りしかないので、それに近い24でも、部分的には決まりそうだな、というように。



2013年8月29日木曜日

Conceptis「最も難しい加算パズル」を解いてみた(1)

先月公開された「世界で最も難しいパズル10選」という記事。世間ではなかなか話題になったようで、Gigazineの転載では、現時点で244ツイート、151のいいね!を集めています。ペンシルパズルの記事としては、異例の注目度といえるでしょう。
しかし自分の知る限り、当のペンシルパズル界ではあまり評判がよくありません。
筆頭に挙げられている「世界で最も難しいナンプレ」がほとんど試行錯誤の繰り返しで解く問題であり、残りのパズルもそうなのではないかと思われること(*1)や、ほとんどがConceptisのパズルから選んだもので「世界で最も難しい」という点に疑いがあることが理由として挙げられます。

自分も、そう思いました。

本当に世界で最も難しいのか?
「世界で最も難しいナンプレ」のように、面倒な試行錯誤をするだけのパズルではないのか?

しかし、パズルは解いてみないとわからない。解かずに憶測で語るのもよろしくない。
そこで、検証してみました。 検証対象は、7番の「最も難しい加算パズル」です。リストのペンシルパズル系のなかで個人的にもっとも好きなパズルであることに加え、これまでにも多数の難問が発表されていて比較が可能であること、見た目で予想がつかないことなどが理由です。

結論だけ先に述べておきます。「世界で最も難しい」とは言いがたいが、試行錯誤はさほど必要ではなく、十分に面白いパズルでした。
その証拠として、このパズルを解く上でポイントになる部分を順に解説してみます。もし興味がわきましたら、これを見ながらでも構いませんので、元の問題に挑戦してみてください。
なお、 ここでは応用的な部分に絞り、基本的な解き方については省略します。wikipediaなどをご参照ください


(1)
まずは、簡単な手筋で埋まるところを探してみます。2マス16と2マス9の交差や2マス16と6マス22の交差があります。ここから、さらにいくつかのマスが連動して確定します。
この段階で、いくつかのマスの候補数字も書いてしまいましょう。このクラスの問題では、候補の書き込みは必須です。また、個人的な習慣ですが、123のマスには○ 、789のマスには△を書いています。

途中経過を右に示します。クリックすると大きい画像で表示されます。
まだまだ序盤です。







(2)
右下でたくさん埋まったので、追いかけてみます。

右図、Aのマスに注目します。このマスの候補は、タテヨコのからみから5or6となります。しかし、仮に6とすると、残りのマスの組み合わせは1と2になり、Bのマスに入る数字がありません。
 したがってAは5、Bは3になります。5が使われたことで、C,Dのマスは6,7と決まり、残りのマスは8or9とわかります。









連動する部分を埋めた状態です。
ここでさらにEとFのマスを見ると、Eは6or7、Fは8or9。
ヨコは6マス24ですので、EF以外の4マスの合計が10以上(同じ列の4マスの合計は10~30になる)になるためには、E+F<=14でないといけません。条件を満たすには、E,Fともに最小の候補を選ぶ必要があり、E=6、F=8

さらに進めるとGのタテ列でも同じように考えることができて、G=6が決定します。

この考え方を【最大最小の手筋】と呼ぶことにします。この後、いろいろな形で出てきます。



こんな感じで、右下の領域はだいたい終了。
まだそんなに難しくないですね。



以下、次回以降に続きます。
当初はまとめてやるつもりでしたが、予想以上に長くなってしまったので、分割します。







(*1) このマスにある数字を入れるとしばらく後に答えがなくなるから他の数字を入れる、という方法。根拠なくこれを繰り返す解き方しかないものは、「難しいかもしれない」が、「面倒なだけ」で、「つまらない」、非常に悪い問題であるとされる
(ここで説明する解き方もある意味同じようなものに見えるかもしれないが、定型的なパターンとして説明することで、ある程度確信を持って解き進めることができる、とされる)