数独日誌101011
おとといの朝日新聞土曜版に世界で一番難しいナンプレ問題のことが書いてありました。この問題については「マーちゃんの数独日記」や「難問ナンプレ・数独を解く」など諸先輩のブログやHPでその存在は知っていたのですが、「世界で一番難しい」という定義がはっきりしないと思って、自分では解いていませんでした。
背理法（仮定法）や試行錯誤やしらみつぶしにやらないと解けないのか、名のあるロジックの組み合わせで解ける問題なのかがわからなかったからです。ただ新聞にまで載ったのにこのブログで話題にしない手はないかな、と思い取り上げることにしました。下がその問題で、表出数字23個の非対称形です。フィンランドの数学者が作ったものだそうです。
005300000
800000020
070010500
400005300
010070006
003200080
060500009
004000030
000009700
土曜版には世界文化社「難問ナンプレに挑戦２」の著者の稲葉直貴さんのコメントが載っていました。「非常に深い分かれ道がある迷路のような難問」だそうです。私も解いてみましたが、２マスで数字が確定し、５についてのFinned Fishが１回使えて、１つのマスから５を排除できただけで、頓挫しました。
論理的に解けるとすれば、おそらく色々な手筋を使って少しずつ数字を排除していく形だと思うのですが、どうでしょう？ それにしても稲葉さんの「分かれ道」という言葉が気になりますね。
| 固定リンク
「趣味」カテゴリの記事
- 数独日誌240908(2024.09.08)
- 数独日誌240901(2024.09.01)
- 数独日誌240825(2024.08.25)
- 数独日誌240811(2024.08.11)
- 数独日誌240804(2024.08.04)
コメント
ikachanさんの手筋の後、左中ブロックで67の隠れ同盟を使って、その後は、試行錯誤を繰り返しつ戻りつで、とても理詰めでは解けませんでした。
こんなのに比べれば、廣済堂の「超難問篇」は言うまでもなく「限界篇」も名前倒れの感があります。
投稿: Tachyon | 2010年10月11日 (月) 16時15分
今日は！初めての投稿です。ナンプレを解くのは初級ですが、アルゴリズムに興味を持っていて、以前解析ソフトをVBAで作ったことがあるので、解いてみました。結果を報告します。
（１）(2,5)=5 と(5,6)=3 がまず求まります。
（２）この段階で、2個の候補をもつセルは、(6,2)=5,9 と(7,8)=1,4 だけですので、問題を４つに分けて進みます。その一つ (6,2)=5,(7,8)=1 のケース（正解）では、さらに (5,8)=5 が求まります。
（３）ここで、2番目の分かれ道に遭遇します。2個の候補を持つセルは3つですが、いづれの組み合わせでも深い迷路にはいります。（PCではどのケースでも解けるのですが、手で解く場合として説明しています）そこで表出数の少ない2,4,6,8,9（いずれも2個）の中から、(4,2)=9、(9,8)=6 を仮定すれば後は難しい手法を使うことなくスルスルと解けます。(4,2)=9、(8,7)=2を仮定すればもっと簡単に解けます。
この問題では、稲葉さんのおっしゃる2度の分かれ道がポイントで、とりわけ2番目の分岐点で(4,2)=9に気がつくかどうか（他にやさしそうな道があるのに）にあるように感じました。
投稿: nko_matsu | 2010年10月11日 (月) 20時44分
nko_matsuさんへ
コメントありがとうございます。新しい方からコメントをいただくとワクワクしてしまいます。試行錯誤で解くにしても相当難しいということですね。はたして論理的に解くことは可能なんでしょうか。
投稿: ikachan | 2010年10月11日 (月) 21時26分
仮定を使わなくては解けない問題でも、たいていの問題は、適切な場所に仮定を適用すれば、すぐに矛盾が導けます。探索木でいえば、層が一段しかない状態です。
しかしながら、この問題は、どこに仮定を適用しても、仮定に仮定を重ねない限り、矛盾を導けません。探索木でいえば、複数の階層がある状態です。稲葉さんも、この意味で「分かれ道」という言葉を使ったのだと思います。
投稿: ニャンチャロフ | 2010年10月14日 (木) 22時19分
ニャンチャロフさんへ
コメントありがとうございます。
お二人のコメントを読むと、どうもこの問題は理詰めで解くのはキビシイようです。
投稿: ikachan | 2010年10月15日 (金) 22時39分
nko_matsuさんへ、はじめまして。
(6,2)=5 は背理法で分かるのですが(といっても矛盾に行きつくには難しいワザを何度も駆使しなければなりませんでしたが)、なぜ (4,2)=9 だと気付いたのかが分かりません。
2,4,6,8,9 (なぜ 1 が除外されたのでしょうか？) をしらみつぶしに（表出数の少ないものとなると調べる候補数は多くなり大変です）調べなくていいとすれば、何かヒントを教えていただけたら有難いのですが。
投稿: Tachyon | 2010年10月16日 (土) 15時57分
この問題の作者は以前にも世界一難しいといわれた問題を作ったそうです。
( http://blog.unfindable.net/?p=1578 )
1 0 0 0 0 7 0 9 0
0 3 0 0 2 0 0 0 8
0 0 9 6 0 0 5 0 0
0 0 5 3 0 0 9 0 0
0 1 0 0 8 0 0 0 2
6 0 0 0 0 4 0 0 0
3 0 0 0 0 0 0 1 0
0 4 0 0 0 0 0 0 7
0 0 7 0 0 0 3 0 0
今回発表されたものに比べると配置はずっときれいですが、これもやはり理詰めでは無理のようです。
投稿: Tachyon | 2010年10月16日 (土) 17時39分
今日は！nko_matsuです。Tachvon さんから質問いただきました。ありがとうございました。
VBAソフトで解いた結果から類推して、もし鉛筆なめなめ解くのならこんな手順になるのではという観点から投稿したものであることをお含みください。
まず最初、この問題を二択仮定法で解くと、６回の仮定が必要で、結果は次のようになります。①(6,2)=5,②(5,1)=2,③(4,2)=9,④(1,1)=1,⑤(1,2)=4,⑥(9,9)=4 です。以下残された52個の空白セルは簡単にわかります。このソフトでは５層までしか一発で計算できませんので、これまでなかったことでまず驚きでした。しかも樹木図を見るとまだ続いているのが6つもありました。
さて、ご質問の(4,2)=9 ですが、いくつかのセルの中で、2個だけの候補を持つセル(5,1)=2,9:(4,8)=7,9:(9,8)=4,6の3個でこのうち(9,8)=6を採用、あと2,4,6,8,9の表出数2個(1は3個です）のものを入れて解いてみました。（正解が分かっているからできるのですが）いづれもfinal answer に到達するのですが、(4,2)=9 が他に比べて早く解に到達したので、そのセルの位置を採用したものです。あまりヒントにならずすみません。
もうひとつの難しい問題もやってみました。何と10層かかって解にたどり着きました。樹木図を見ても5層ではまだ生き残りが多く、こちらのほうがむづかしいのでは？もっとも仮定法では仮定する数字によって随分左右されるので、どうなのでしょうか？また、面白い問題があれば教えてください。 では。
投稿: nko_matsu | 2010年10月17日 (日) 12時30分
nko_matsuさんへ
ご返事ありがとうございます。
しかしながら、今回発表された問題の方で、まだお尋ねしたい事があります。
表出数字の１は3個ということですが、(5,2)(3,5)以外に、どうすれば、どこが１になるのかが分かりません。
また、(9,8)=1,4,6 からどうすれば、(9,8)=4,6となるのかが分かりません。
その辺をもう少し説明して頂けないでしょうか？
投稿: Tachyon | 2010年10月23日 (土) 12時44分
Tachyonさんへ
こんにちは！nko_matsuです。
わたしのコメントの説明不足のため、余計な時間を使わせたことをおわびします。
最初のコメントの（２）に書きましたが、この段階で、2つしか候補を持たないセルが2つあるので、４通りの問題として取り扱っています。その中のひとつが正解で、(6,2)=5,9 (7,8)=1,4 で (6,2)=5,(7,8)=1 は仮定した数字です。いうなれば二重仮定と呼ぶのでしょうか。したがって、同じブロックにある(9,8)から１の候補はなくなります。（仮定法では仮定する数字のセルの位置と個数によって随分左右されるので、このソフトでは5通りの方法から選択できるようにしています。）
投稿: nko_matsu | 2010年10月24日 (日) 12時19分
nko_matsuさんへ
なるほど二重仮定だったのですね。すみません、前のコメントで見落としていました。
しかしながら私には、(6,2)=5 (7,8)=4 では矛盾は導けないのですが...
そこのところはnko_matsuさんのソフトではどう処理されているのでしょうか？
投稿: Tachyon | 2010年10月24日 (日) 12時56分
Tachyonさんへ
今晩は！ご質問の件お答えします。行き詰まった段階でfinal_answer_checkというマクロで正解かどうかを判定します。まだ空白セルがある場合には、候補の数を調べます。もしあるセルで候補が０になれば、そのルートは行きずまりです。（このケースがもっとも多いです）すべての空白セルで2個以上の候補を持てばそこからまた新しいルートに分かれます。
今回の残った3ケースで、ご質問の(6,2)=5,(7,8)=4 のルートは５層目でまだ2ルート残りますが、さらに続けるとすべて行き詰まります。不正解ルートでここまで引っ張るとは驚くべき粘り腰です。
一方、すでにご確認のようですが、残る２ルートは直ぐに行きづまります。今回のご質問がきっかけで、別の多数解を求めるソフトにかけてみて本問題が唯一解であることを確認しました。
投稿: nko_matsu | 2010年10月24日 (日) 22時25分
nko_matsuさんへ
> ご質問の(6,2)=5,(7,8)=4 のルートは
> ５層目でまだ2ルート残りますが、
> さらに続けるとすべて行き詰まります。
> 不正解ルートでここまで引っ張るとは驚くべき粘り腰です。
うわぁ...さらに多重の仮定が必要なのですか。
背理法等で(7,8)=1を確定させるのはとても大変なようですね。
お手数をおかけしたことをおわびします。ありがとうございました。
投稿: Tachyon | 2010年10月25日 (月) 20時30分
この問題に関して、私の今の能力で理詰めで解けるのは、
(2,5)=5 と(5,6)=3 が確定した後、左中ブロックでの67の隠れ二国同盟と右中ブロックを本体とする2-String Kiteで(6,2)の５を除外(ikachanさんの場合はFinnedFish）までですが、この後、nko_matsuさんのコメントを参考にして、以下のように解いてみました。
ちょっと幸運すぎる解き方ですが...
[単層仮定法]
(6,2)=5,9に注目
(6,2)=9 → 以下の手筋で矛盾
二国同盟
2-String Kite
W-Wing
NiceLoop x6
NiceLoop+Group
X-Cycle+EmptyRectangle
背理法により(6,2)=5 →(5,8)=5
[二重仮定法]
左中ブロックでの8((4,2),(5,3))と４行での2((4,2),(4,8))に注目
(4,2)=8,(4,2)=2 → 当然矛盾
(4,2)=8,(4,8)=2 → 不明
(5,3)=8,(4,2)=2 → 以下の手筋で矛盾
三国同盟 x2
隠れ二国同盟
XY-Wing
UniqueRectangle
HiddenRectangle
FinnedFish
SwordFish
NiceLoop x4
(5,3)=8,(4,8)=2 → 以下の手筋で矛盾なく埋まる
二国同盟 x4
隠れ二国同盟
SashimiFish x2
XY-Chain x2
W-Wing
SueDeCoq
NiceLoop x16
NiceLoop+Group x5
ALS-XZ
(http://fukujin2k.blog88.fc2.com/blog-entry-92.htmlを参照)
KrakenFish x4
HiddenRectangleとKrakenFishはミシチャンのサイトにはありませんが、SudopepiaやHoDoKu(http://hodoku.sourceforge.net/en/techniques.php)を参照してください。
投稿: Tachyon | 2010年11月 3日 (水) 15時37分
すみません、上記のコメントで以下の部分について訂正します。
[誤]
> 左中ブロックでの8((4,2),(5,3))と４行での2((4,2),(4,8))に注目
>
> (4,2)=8,(4,2)=2 → 当然矛盾
>
> (4,2)=8,(4,8)=2 → 不明
>
> (5,3)=8,(4,2)=2 → 以下の手筋で矛盾
> 三国同盟 x2
> 隠れ二国同盟
> XY-Wing
> UniqueRectangle
> HiddenRectangle
> FinnedFish
> SwordFish
> NiceLoop x4
>
> (5,3)=8,(4,8)=2 → 以下の手筋で矛盾なく埋まる
[正]
左中ブロックでの8((4,2),(5,3))と４行での2((4,2),(4,9))に注目
(4,2)=8,(4,2)=2 → 当然矛盾
(4,2)=8,(4,9)=2 → 不明
(5,3)=8,(4,2)=2 → 以下の手筋で矛盾
三国同盟 x2
隠れ二国同盟
XY-Wing
UniqueRectangle
Hidden(Unique)Rectangle
FinnedFish
SwordFish
NiceLoop x4
(5,3)=8,(4,9)=2 → (4,2)=9となり、以下の手筋で全て矛盾なく埋まる
投稿: Tachyon | 2010年11月 6日 (土) 15時51分
すみません。もう一箇所間違っていたところがありました。
[誤]
> 右中ブロックを本体とする2-String Kiteで(6,2)の５を除外
[正]
右中ブロックを本体とする2-String Kiteで(9,2)の５を除外
投稿: Tachyon | 2010年11月14日 (日) 12時17分
この問題は二重仮定法を使わなくても、３回の単層仮定法(二択)を使って解けることが分かりました。
(依然として幸運すぎる解き方ですが...)
一回目:
訂正した理詰めの手順の後、上記のコメントの[単層仮定法]と同じです。
二回目:
第４行での2((4,2),(4,8))に注目
(4,2)=2 → 以下の手筋で矛盾
三国同盟 x2
隠れ二国同盟
XY-Wing
UniqueRectangle
HiddenRectangle
FinnedFish
SwordFish
連続NiceLoop定理①②
不連続NiceLoop定理④ x2
不連続NiceLoop定理⑤
(NiceLoopについては、びーにぃのWiki攻略本 http://blogs.yahoo.co.jp/bea_nies/62328396.htmlを参照)
背理法により(4,8)=2→(4,2)=8,9
三回目:
(4,2)=8,9に注目
(4,2)=8 → 不明
(4,2)=9
上記のコメントで(5,3)=8,(4,9)=2とした場合と同じです。
投稿: Tachyon | 2010年12月11日 (土) 17時50分
すみません。また間違えてしまいました。
[誤]
> 第４行での2((4,2),(4,8))に注目
[正]
第４行での2((4,2),(4,9))に注目
[誤]
> 背理法により(4,8)=2→(4,2)=8,9
[正]
背理法により(4,9)=2→(4,2)=8,9
投稿: Tachyon | 2010年12月21日 (火) 19時59分
この問題は単層仮定法(三択)を一回使っただけでも解けることが分かりました。
基本的な技で(2,5)=5 と(5,6)=3 を確定し、左中ブロックでの67の隠れ二国同盟と右中ブロックを本体とする2-String Kiteで(6,2)の５を除外(ikachanさんの場合はFinnedFish）した後、
上中ブロックに三つある候補数字２(1,5)(1,6)(3,6)に注目し、その中の(1,5)を２とすれば以下のテクニックで解けます。
二国同盟
三国同盟
四角の対角線
X-Cycle
Finned Fish x2
Finned Sword Fish
Nice Loop x11
Grouped Nice Loop x3
(以下の２つのテクは、
http://fukujin2k.blog88.fc2.com/blog-entry-92.htmlを参照)
ALS XZ-Rule
ALS XY-Wing x2
Triple Cell Forcing Chain
(http://www.sudokuwiki.org/Cell_Forcing_Chainsを参照)
Unit Forcing Chain x2
(http://www.sudokuwiki.org/Unit_Forcing_Chainsを参照)
依然として幸運すぎる解き方ですが...
投稿: Tachyon | 2013年7月21日 (日) 17時50分