« 数独日誌130818 | トップページ | 数独日誌130903 »

数独日誌130829

   世界文化社「西尾徹也の世界で一番美しくて難しいナンプレ5」(以下「世界一5」と略します)36~39、66~74の報告です。解き始めから苦戦して、なかなか記事が書けませんでした。「世界一4」と比べて、特に難化したわけでもないようなんですが、見落としが多く、3,4題は1回目ではうまくいかず、再チャレンジしてなんとか攻略しました。

   「世界一4」については「数独日誌120831」などを参照してください。なお過去のブログ記事は下のページからジャンプできます。
http://ikachanzanmai.private.coocan.jp/burogukiji-ichiran.html

   以下私の使った手筋です。71,72などXYZ-Chainを使った問題は、もっとすっきり解答できたのではないかと思います。別の解き方をした方、ぜひコメントをいただけたらと思います。次回はSuper HeavyとDevilishを7題ずつ報告したいと思います。

3国同盟 37,38,39,68,74
3国同盟×2 70 
4国同盟(隠れ3国) 36
4国同盟 68,74
四角の対角線(X-Wing) 37,39,66,68
四角の対角線(3行 Swordfish) 37,70
四角の対角線(3行 Swordfish)×2 36,68
Simple Chain 37,39
XY-Wing 37,66,69,73
XY-Wing×2 70,74
XY-Chain 67
Finned Fish 72
Sashimi Fish 38,68
Sashimi Fish(3行) 71,72
XYZ-Chain 71,72

|

« 数独日誌130818 | トップページ | 数独日誌130903 »

趣味」カテゴリの記事

コメント

こんにちは htms42 です。
天気の良くない日が続きますので家にいる率が高くなります。
私も西尾徹也の本を手に入れてきました。

71,72 やってみました。
72のほうがやさしいですね。
普通の手筋でいきついたところ(さて、これからどういう風にしようかと立ち止るところ)の局面が72のほうが少し簡単です。
まず72からです。
右端の3列で7,3,1の関係を見ます。1がたくさん余っています。7は各ブロック、2個ずつですからぴったりです。3は右下c9に余りがあります。7のペアについて1,3の入り方を調べるとr7c8、r7c9で(17)の2国同盟が成立していることがわかります。r7c2は3であることが決まります。
これで終わりまで行きます。

71
r7に(48)の2国同盟があります。
r7c2に4または8を入れます。
4をいれます。r5c2が1になります。r6c1の1は消えます。
8を入れます。r6c1が8になります。
r6c1の1はどちらにしても消えてしまいますから削除してしまっていい数字です。r6c7は1であることが確定します。(これは「~ループ」という方法でも見つかるかもしれませんね。)

xy-wingでも井桁の論理でも「2つの可能性で調べて行ったとき、共通に消えるものがあれば消してしまっていい」という論理を使っています。共通に消えるということが起こるためには2つの可能性で進めていった道筋が同じところを通るということが成り立っていなければいけません。ループが出来上がっていることを使っているのです。「~ループ」という名前のついているものだけがループではありません。

Inkara氏の作った問題では
2つの可能性について手を進めていった時の道筋が重ならないのです。重なる可能性を徹底的に排除しています。矛盾に突き当たるまで仮定を積み重ねながら手を進めていくしか方法がないというのはここから出てくることです。ただすべてをコンピュータにやらしていますから排除のアルゴリズムから漏れているようなペアがあれば道筋の交差が起こる可能性があります。
出回っている解法はすべてアルゴリズムで考慮されている可能性があります。漏れているものというのはどういうものになる可能性があるのか、ちょっとよくわかりません。

その可能性の1つは2つの異なる数字が異なるセルに入っているというペアの作る2択です。ふつうは1つのセルに2つの数字が入っているというペアか、同じ数字が異なるセルに入っているというぺアです。

投稿: htms42 | 2013年8月31日 (土) 12時55分

htms42さんへ
コメントありがとうございます。
私の住んでいる神奈川県は昨日今日と猛暑復活といった感じで、体がついていけない感じです。

ところで72番は背理法を使わないで解かれたのでしょうか?

『7のペアについて1,3の入り方を調べるとr7c8、r7c9で(17)の2国同盟が成立していることがわかります』

この部分がよくわかりません。もう少し詳しく説明していただけないでしょうか?

他にもわからない点があります。
『xy-wingでも井桁の論理でも「2つの可能性で調べて行ったとき、共通に消えるものがあれば消してしまっていい」という論理を使っています』

XY-Wingは3つの2択マスの候補数字がxy,yz,zxと連鎖しているとき、第2のマスにyが入る場合も、zが入る場合も第1のマスと第3のマスの両方を臨むマスからxが除外できる、ということで、確かにこの論理を使ってますよね。

問題は井桁の論理(X-Wing)のほうです。これは4つのマスは2択マスである必要はないですし、当該数字が除外できるマスも同じく2択マスである必要はないので、この手筋と、

「2つの可能性で調べて行ったとき、共通に消えるものが
あれば消してしまっていい」

という論理はどうつながっているのでしょうか?
もしかしてミシチャンさんのサイトにある考え方を使って
いるのでしょうか?

「n国同盟とX-wing系の解法は全く同じアルゴリズムで処理できます」
http://www.geocities.jp/master_mishichan/same.html

投稿: ikachan | 2013年8月31日 (土) 18時59分

ikachan様
72
ちょっと端折った書き方をしてしまったようですね。
r1c7c8に77ノペアがあります。r7c8c9にも77のペアがあります。間をつなぐ形でr6c7、r4c9に7が入っています。各ブロックに2つずつですから入り方は2つのグループに分かれます。これに連動して右下のブロックの1の入り方も決まってしまうのです。3が間をつなぐ役割をしています。1はr7c8c9にしか入りません。これで(1、7)の2国同盟が成立します。
言葉で言っても分かりにくいかもしれません。r1c7、r1c8に7を入れてみて色分けしましながらたどってみればわかりやすいです。どちらが解であるかを決めようとしているのではありません。つじつまの合った配置はどのようなものになるかを調べているだけです。数独を解いていくときの基本となるのは「余分な候補数字を減らしていく」という作業です。その結果としてどこかのセルで候補数字が一つになればそのセルに入る数字が確定します。2択を選んで調べていくというのはこの余分な数字を減らしているという作業がやりやすいからです。たとえばここで出てきている「どちらにしても」の論理は3択ではむつかしいです。2択であればどちらかが解につながっているはずだということは確かですが直接解を求める作業をやろうとはしていません。とりあえずつじつまの合う数字配置はどうなっているかを調べて候補数字を減らしていこうという論理です(やっていく途中で矛盾に突き当たる場合もありますす、・・・)。「背理法」という言葉が誤って持ち込まれてしまった理由の一つはこれを解を求める作業だと考え、矛盾に行き着くことを目指している作業だと思い込んでいることにあるようです


井桁の論理

井桁の論理は定員確定系の一種です(本当はすべてが定員確定系であるということができるのですが、・・・)。
A・・・・B
a・・・・a     2つだけ(1)
・・・・・・
a・・・・a     2つだけ(2)
・・・・・・
a・・・・a・a・a たくさん(1)
a・・・aa     たくさん(2)

A列、B列に数字aが入っています。
2つだけしか入っていない行が2つあります。
この2つの行で定員は一杯になります。
下のaがたくさん入っている行のA列、B列にはaを入れることができません。これが普通の説明だと思います。「どちらにしても」の論理は使っていないように見えますね。でも2つの可能性についてつじつまの合う配置はどうなっているだろうかという立場で調べると「たくさん(1)」「たくさん(2)」のA列、B列にあるaは共通に消えるaになっています。「2つだけ」という行があるのですから2択です。「定員いっぱいになっている」という言葉を論理で表現し直していることになります。

これは3×3、または4×4の数字の配置に拡張できます。「~fish」という名前がついているものです。(こういう同じ論理で出来上がっている解法に別々の名前を付けるというのはよくありません。名前は符号でしかないという立場、やはり内容を表すようなものであるべきだという立場があるようですが、私は符号説には賛成しません。2国同盟、3国同盟、4国同盟に「太郎」、「花子」、「次郎」という名前がついていればどうでしょう。ikachan様は四角の対角線の2×2、3×3、4×4と同系統であるということがわかる名前を付けていますね。いいことだと思っています。w-wingという名前、~fishという名前は捨ててしまうほうがいいと思います。)
3×3、4×4は2択ではありません。2択で済む場合もありますが、基本的には3択、4択が含まれています。でもどちらにしても消えるという論理は使っているのです。
3択の場合は「3つの可能な場合について数字のつながり具合を調べていったときに3つで共通に消える数字があれば消してしまってもいい」という表現になります。4択でも同様です。

3択、4択が論理の中に含まれているというのが他の解法と性格が異なるところです。普通の解法には出てきません。3択、4択が出てくるのにややこしくならない理由は1つの数字の中での関係を見ているという制限があるからです。3択、4択を2択で表現しようとすれば2段階に仮定を使わないといけなくなります。普通ならものすごくややこしくなります。でもその仮定が1つの数字の中の関係に閉じ込められている、他の数字には影響を及ぼさないようになっていうるということでややこしくなるのが避けられています。でも、いちいち共通に消えることを確かめるということはやられていませんね。公式として「こういう配置の時はここの数字は消える」とだけで使われているのがふつうです。証明は省略して「2×2の場合と同様に」とだけ書かれている場合が多いです。
(こういう風に及ぶ範囲は限られているときは3択、4択を使ってもややこしくならない可能性があります。2つの数字だけが関係する、または3つの数字だけが関係するが閉じているような数字配置が見つかれば仮定の積み重ねでややこしくなることを防ぐことができます。Inkara氏の問題を解くのに役に立つのではないかと期待しています。)


投稿: htms42 | 2013年9月 1日 (日) 12時24分

ちょっと補足です。

もしかしてikachan様は2択をもっぱら「同じセルに2つの数字が入ったもの」と考えておられるのではないでしょうか。「同じ数字が異なる2つのセルに入っている」のも2択です。井桁の論理はこちらです。井桁の論理(四角の対角線の論理)の方法は1つの数字についての関係だけを追いかけています。同じセルに他の数字がどれだけ混ざって入っていても関係がないのです。これは目立った特徴です。パワーのある解法であるということが言える源になっています。候補数字の数が多くてこんがらがってしまっているような局面を整理してくれる解法です。候補数字を書き出していく作業がまだ完結していなくても1つの数字だけで見れば使うことができるという状況になっている場合もよくあります。早い目に使うと後が楽になります。94番では9についての井桁の論理の適用を早くやっておくとものすごく楽になりました。(普通にやっていてややこしい状況になりましたのでやり直しました。しょっちゅうやり直しをやっています。一度できても別の道筋を探るというのもやっています。一度でできなければいけないというものではありません。)

投稿: htms42 | 2013年9月 1日 (日) 13時59分

htms42さんへ
ていねいなコメントありがとうございます。

72番についてですが、
要するにr7c8の17の2択マスについて、ここに7が入ると、r1c7が7、r3c9が3、r9c7が3、よってr7c9が1となる。またここに1が入るとr7c9が7になるということですね。了解しました。

私は「2択マス」という言い方で、1つのマスの候補数字が2つまで絞れた状態、を表していましたが、htms42さんのいう「2つの可能性で調べて行ったとき」というのは「同じ数字が異なる2つのセルに入っている」という場合も含んでいるわけですね、これも納得しました。

なお文章の途中でニコリ社の編集長についての文章が登場
しますが、何の根拠もない、このような好戦的な物言いは
私が不愉快になるので、やめていただきたいです。この
部分(前後の部分も含めて)は管理人の責任で削除させて
いただきました。

投稿: ikachan | 2013年9月 1日 (日) 15時10分

 私はオーソドックスな解き方が好きですし、それしかできないので、いつも通りの解き方です。
 71は、R2C2(1)=R3C1(1)-R6C1(1)=R6C8(1)-R9C8(1)=R9C7(1)でR2C7から1を削除。R5C6(4)=R5C2(4)-R7C2(7)=R7C4(4)の2-StringKiteでr9c6から4を削除。r6c3(42)-r6c5(28)-r9c5(84)のXY-Wingでr9c3から4を削除。
 72は、r4c2(6)=r9c2(6)-r8c1(6)=r4c9(6)の2-StringKiteでr4c9の6を削除し、r4c9(17)=r6c7(7)=r1c6(73)=R3C9(3)によりR3C9から1を削除してR3C9=3。

投稿: まあ坊 | 2013年9月 1日 (日) 22時52分

ikachan様

2択についての補足です。

同じ数字aが異なるブロックにあるセルA,Bに入っているとします。この行ではここにしか入っていません。ほかの行にはたくさんありますがとりあえずAの下について見ればC,D,Eに入っているとします。

A---B   (ここはaの2択です。)
------

------

------

aがBに入るとしてつながりを見ます。C,D,Eのどこに行くかを探る方向で調べていきます。Dにあるaに行き着いたとします。C,Eにあるaは消してしまっていいことがわかります。
B → Dの道筋は他の場所の数字の配置によって変わります。C,Eにあるaを消してしまっていいというのはどういう道筋を通ってDに行き着いたかによらず成り立つことです。

この道筋が一番短くなるのはどういう場合でしょうか。
「Dのある行ではBの下にしかaがない」という場合です。この特別な場合が「井桁の論理」に当てはまります。でも井桁の論理にしか使えないと思ってしまうのはもったいないです。

ミシチャンさんのサイトに「仮定法には戦略がない」と書いてありました。でも、「BからスタートしてC,D,Eの中のどこに行きつくかを探れば行き着いたところ以外の2つの場所にある候補数字は消すことができる」、これは「戦略」だと言ってもいいのではないでしょうか。具体的な道筋は決まっていなくてもどういうことを目指して道筋を探っていくかを示しているのですから「戦略」なわけです。井桁の論理はその実行形の一つになっています。


投稿: htms42 | 2013年9月 2日 (月) 10時15分

まあ坊さんへ
コメントありがとうございます。
2-String Kiteをよく使われていますね。私は最近あまり使っていませんでした。自分の好きな(見つけやすい)手筋というのがあるようです。

投稿: ikachan | 2013年9月 2日 (月) 15時54分

ikachanさんへ

2-StringKiteは、強リンクのペアを探すと結構みつかります。SashimiFishは強リンクのペアが平行になっていますが、2-StringKiteは、それ以外の状態です。ikachanさんの解き方は、候補数字を全て書き入れる直前までは私と同じのようなので、その段階で探すといいと思われます。

投稿: まあ坊 | 2013年9月 2日 (月) 20時33分

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: 数独日誌130829:

« 数独日誌130818 | トップページ | 数独日誌130903 »