- ベストアンサー
世界で一番むつかしい数独問題とは？
- 東大の渡辺氏のサイトに「世界で一番むつかしい数独の問題」というのが載っているのを見つけました。
- 渡辺氏はこれよりもむつかしい問題を作ろうと考えたようです。
- 「世界で一番むつかしい問題」を作ろうとしている意味とはどういうものでしょう。数独というゲームとどういう関係があるのかもよくわかりません。
- みんなの回答 （5）
- 専門家の回答
質問者が選んだベストアンサー
将棋の世界ではプロがコンピュータに2連敗したそうな。詰め将棋の世界でも問題作りにコンピュータが使われている様です。（もっぱら解の検証に）ですが、詰め将棋の難しさやおもしろさまではコンピュータが判断してくれないようです。（今のところ） 実際、詰め将棋界で最も権威のある賞「看寿賞短編部門」を平成元年に取った問題は、なんと3手詰めにもかかわらず、回答者183人中、誤答98人だったそうです。 また、逆に長手数で有名なミクロコスモスは1525手詰みだそうです。これもコンピュータで解けるそうです。問題を作ったのは人間です。それにしても1525手詰みの問題にチャレンジする人がいるのかしらねぇ。おもしろいかどうか・・・ いずれににしても、詰め将棋の世界においては、何らかの名作の基準はあるようです。意外なところに成るとか、合駒に意外性があるとか、初手が奇抜とか。といっても感性の問題ですから明確な定義はあるわけじゃないです。 脳生理学や心理学が進歩すると、難しさやおもしろさといった感情（感性）に関わる領域も数学的にモデル化されるのかもしれませんねぇ。 数独とは詰め将棋は性質が違いますが同じパズルの分野に入るものとして例にあげました。
その他の回答 (4)
- alice_44
- ベストアンサー率44% (2109/4759)
結局、貴方(Inkara氏や渡辺氏ではなく)が、 「むつかしさ」＝「深さ」＝ トラックバックの段数 と考えているのか否か？がハッキリしないし、 貴方の探したいものが、「むつかしさ」の定義なのか 「面白さ」の定式化なのか？も解らない。 貴方自身による「むつかしさ」の定義は、書かないの？
お礼
渡辺氏に問い合わせてみました。 渡辺氏は解に至るまでの手順数の多い問題を作ることを目的にしているようです。仮定の積み重ねがあれば場合の数が増えますから手順の数も多くなります。仮定を置いた後の進め方は基本解法だけに限定しているようです。そうすることによって必要な仮定の数が増えるようにしています。 これが普通の問題の解法とは違うところです。基本解法だけでは解けそうに見えない問題でも特別な数字の配置に着目すると仮定の積み重ねをやるよりは簡単に解くことができるということを解法のポイントにしています。離れたところにある数字の特別な関係が手を進める手掛かりになるということです。でも見つけにくくなっています。仮定を使う場合も並立的です。手順の数を多くするというよりは少なくするほうに関心があるようです。 中には仮定が積み重ねになっているものもありますが仮定の及ぶ範囲が限定されるようになっています。モデュール化されているといってもいいでしょう。 基本解法に限定するというのはそういう約束をするというのではなくて、基本解法しか使えないような局面をプログラム的に作り出しているということのようです。Ｉｎｋａｒａ氏の問題を解いたときには仮定を置いて出てきた局面の中でｘｙ－ｗｉｎｇやｓｗｏｒｄ ｆｉｓｈのような手筋が表れていないかどうかをチェックしていて時間がかかりました。そういうことは一切考えずに基本解法だけで解いていって、行き詰ったらどんどん仮定を置くというやり方に開き直るとかえって速く解くことができるのです。 ただ、やはり、解く立場を考えずにプログラム的にだけ問題を考えていると手で解けば簡単な問題が、指標的にはむつかしい問題であるという結果になって、こけてしまうということも起こってしまいます。 渡辺氏のサイトからＩｎｋａｒａ氏サイトを開いてみました。ｔｏｐ１０という項目を開くとｗｏｒｌｄ’ｓ ｍｏｓｔ ｄｉｆｆｉｃｕｌｔという問題が載っていました。２０１０年、２０１２年の問題とは異なります。たぶん最新版だと考えていいでしょう。そうだとすると２０１２年よりも難しいはずです。Ｉｎｋａｒａ氏の基準に従えば２０１２年の８段を超えているはずだと考えました。ちょっとやってみるのをためらいました。でも紙に書いてＰｅｎｃｉｌ Ｍａｒｋｓを完成させてみるとそんなに難しいようには見えませんでした。たくさんコピーを用意して仮定を置く作業に取り掛かったのですが５段の仮定で解に行きつきました。「？？？？？・・・」でした。コピーした紙が余ってしまいました。Ｉｎｋａｒａ氏も手を動かして解こうとはしていないようですから判断ミスをやってしまったのかもしれません。
補足
Ｉｎｋａｒａ氏の新しい問題（２０１３年版とします）と解いてみた結果を載せておきます。 ２０１２年版の解答はＩｎｋａｒａ氏のサイトに載っていますが２０１３年版については載っていないようです。 問題（２０１３年） １００ ００７ ０９０ ０３０ ０２０ ００８ ００９ ６００ ５００ ００５ ３００ ９００ ０１０ ０８０ ００２ ６００ ００４ ０００ ３００ ０００ ０１０ ０４１ ０００ ００７ ００７ ０００ ３００ 解 ２０１２年版に比べると易しそうだというのは問題を見比べてみるだけでもわかるのではないでしょうか。解くのに必要な仮定の積み重ねの段数は２０１２年版が８、２０１３年版が５でした。”ｗｏｒｌｄ’ｓ ｍｏｓｔ ｄｉｆｆｉｃｕｌｔ” という言葉を使うことはできないのです。 （Ｉｎｋａｒａ氏のサイトのｔｏｐ１０には深さが８と書かれています。プログラム（アルゴリズム）に不備がありそうです。） １６２ ８５７ ４９３ ５３４ １２９ ６７８ ７８９ ６４３ ５２１ ４７５ ３１２ ９８６ ９１３ ５８６ ７４２ ６２８ ７９４ １３５ ３５６ ４７８ ２１９ ２４１ ９３５ ８６７ ８９７ ２６１ ３５４
- alice_44
- ベストアンサー率44% (2109/4759)
発表された「むつかしい」を批判しているよりも、 それを「易しい」と評価するのであれば、自分の「むつかしい」を まづ定義してみることが建設的かなあ…と。 トラックバック愛好者ではない、数学ファンより。
お礼
ありがとうございます。 数独、ナンプレは仮定を積み重ねていけば解けることはわかっています。 でも、私がふだんやっているときには仮定の積み重ねはやりません。 面白くないのです。 仮定を置くことなしには数独を解くことができません。一段の仮定は使います。 Ｉｎｋａｒａ 氏の問題（Ｂ）は一段の仮定では何らの結論も得られないようになっています。分岐を繰り返して枝の一つずつをチェックするしかありません。徹底しています。 私がやった時、８段の仮定の積み重ねで解に行き着きました。渡辺氏のサイトに「深さ」が８となっているのに対応すると思います。でも難易度の指標になるのは「深さ」ではなくて「幅」であるとも書かれています。手でやる場合は「深さ」だけを指標にしても十分だと思います。 仮定の積み重ねの段数を増やしてむつかしさの程度を上げるというのは数独としての面白さとは関係のないことだろうと思います。ただ、問題として成立する限界を探るというだけの意味しかないでしょう。でも、唯一解が存在するという条件で ９×９＝８１ の盤面の上で作るのですから上限が存在するでしょう。可能だとしても１０段ぐらいがせいぜいではないでしょうか。 ※もしかしたら、Ｉｎｋａｒａ氏の深さ８が上限になっているのかもしれません。 ※※渡辺氏の初めの問題は深さが１０になっていました。しかし、仮定の並列でわかることまで積み重ねの段の一つに組み入れてカウントしてしまっているのでおかしくなってしまったのです。手でやれば簡単に解くことができるというのは一段の仮定が並立的に使われているだけだからです。
- MagicianKuma
- ベストアンサー率38% (135/348)
質問と思われるのは次の2点？ ＞「世界で一番むつかしい問題」を作ろうとしている意味とはどういうものでしょう。 渡辺氏に聞くのが早いでしょう。想像するに「そこに山があるから。」位のことでは？ ＞数独、ナンプレの本を出版している人たちはどういう風に考えているのでしょうか。 これも関係者に聞くしかない。想像するに、「話題作りになるので大いに結構。」位のことでは？ 数独 一ファンより。
お礼
ありがとうございます。 ＞想像するに「そこに山があるから。」位のことでは？ 渡辺氏の場合、「エベレストに上るといって出かけて富士山に上って帰ってきた」というレベルなのではないでしょうか。もしかしたら、駿河の富士ではなくて、近江の富士だったのかもしれません。 研究用のコンピュータを２４時間も動かして、・・・ あきれました。 昔、私が学生だった頃、大学の計算センターの使用料が１分間２００円でした。大卒の初任給が２万円ぐらいの時です。
- fumiuchip
- ベストアンサー率13% (119/898)
そうですか。お疲れ様です。
お礼
ありがとうございます。 詰将棋での例、参考になります。 将棋の場合、取った駒を再利用できるというのがチェスとは違うところだと言われています。 数独の場合、手が進むと局面がどんどん狭くなっていきます。 ９×９＝８１というという広さの盤というのは将棋と同じなのですが、初期設定の数字が２０個ほどありますからスタート場面での広さは６０ほどです。ここに候補数字が入っています。数独を解くというのはこの候補数字の数を減らしていくという作業です。数字と数字の間に成り立つ位置関係によって候補が制限されていきます。「矛盾を生じない位置関係はどういうものになるか」という判断です。あるセルに入る数字が確定するというのはその結果です。１つの数字が決まると手が進みます。局面が狭くなります。仮定をおいて数字の決まり具合をチェックするという場合でも同じです。際限なく手順が伸びるということは不可能です。（＃３のお礼欄に書きましたが）仮定を積み重ねるとしても１０段ぐらいが限界ではないかと思います。千日手のような堂々巡りは「唯一解が存在する」という条件が置かれていますから出現しません。 二分法で仮定を置いていくのですから、１０段であれば ２^10＝１０２４ の場合が出現すると考えそうですがそうではありません。矛盾に行き当たるまでの仮定の段数のほとんどは１０以下です。２つに分けて数字を入れて手をすすめた時、手の進み方のいい方は、たいてい矛盾に行き着きます。進み方がいいというのは重ねて置かなくてはいけない仮定の入る余裕が少なくなるということだからでしょう。少し進むとすぐに行きづまるという事情があるから仮定の段数が増えていくのです。 渡辺氏に問い合わせてみましたが目標としているのは「仮定の積み重ねの段数を増やすこと」のようです。１つの仮定の中で用いる解法は基本的な定員確定系だけになっているようです。私が感じた「面白くない」ということの理由はこの点にありそうです。仮定の部分を除けば市販の普通の上級問題ぐらいのレベルです。難問とか超難問とかではありません。ただ仮定を積み重ねないと解けないということで解き切るのにものすごく時間がかかるようになっています。同じ論理の作業をただ繰り返すだけですから「面白くない」と感じたのでしょう。 渡辺氏は「手で解けるか、解けないか」とか「人が難しいと感じるか、感じないか」とかは考えていないと言っています。 １０段程度が段数の最大値であればすべて手で解くことができる範囲にあるのではないかと私は考えています。 これはＩｎｋａｒａ氏の８段の問題を解いてみた結果からの予想です。