「世界で一番むつかしい数独の問題」・・・

東大の渡辺氏のサイトに「世界で一番むつかしい数独の問題」というのが載っているのを見つけました。フィンランドの数学者、Inkara氏が２０１０年、２０１２年に発表したものだそうです。
http://apollon.issp.u-tokyo.ac.jp/~watanabe/samp …

（A）２０１０年　　　　　　　　　　（B)２０１２年
００５　３００　０００　　　　　　　８００　０００　０００　　
８００　０００　０２０　　　　　　　００３　６００　０００
０７０　０１０　５００　　　　　　　０７０　０９０　２００

４００　００５　３００　　　　　　　０５０　００７　０００
０１０　０７０　００６　　　　　　　０００　０４５　７００
００３　２００　０８０　　　　　　　０００　１００　０３０　

０００　５００　００９　　　　　　　００１　０００　０６８
００４　０００　０３０　　　　　　　００８　５００　０１０
０００　００９　７００　　　　　　　０９０　０００　４００

※空白には「０」を入れています。

渡辺氏はこれよりもむつかしい問題を作ろうと考えたようです。ス＾パーコンピュータを動かして作ったのが次の問題です。
（C)２０１３年３月
０６１　００７　００３
０９２　００３　０００
０００　０００　０００

００８　５３０　０００
０００　０００　５０４
５００　００８　０００

０４０　０００　００１
０００　１６０　８００
６００　０００　０００

しかしこれは市販の問題集に載っている上級レベルの問題です。これを「世界で一番むつかしい問題」だと判断して発表したのですから計算機を動かすアルゴリズムに初歩的なミスがあった、または渡辺氏の数独の理解の程度に致命的な欠陥があったということになりそうです。（渡辺氏は自分では数独の問題を解こうとはしていないようです。コンピュータの出した数値だけをそのまま判断材料にしているのです。普通に解けば簡単にわかる不具合が見つからないままになっています。）

（C)が簡単に解くことができる問題だったということが分かったので作り直したというものが追記の形で発表されています。
（D)３／２２付け　追記
０８０　０００　１５０
４０６　５０９　０８０
０００　００８　０００

０００　０００　０００
００２　０７０　００３
３００　８０１　０００

９００　１７０　０００
６００　０００　００４
１５０　０００　０９０

Inkara氏の（A)(B)に比べると格段にやさしいです。

「世界で一番むつかしい問題」を作ろうとしている意味とはどういうものでしょう。
数独というゲームとどういう関係があるのかもよくわかりません。
「むつかしい」ということがどういうことかも十分に吟味されているとは思えません。
解くのに必要な時間にはかなりの違いがあります。（B)>(A)>(D）です。でも解くのに必要な時間の違いがむつかしさの違いでしょうか。（B)を解くのには時間がかかります。でもむつかしくはありません。面倒なだけです。同じ論理をただ繰り返し使っているだけです。仮定の段数が多いので場合の数が多くなり、可能性のチェックに時間がかかるのです。ゲームとしての面白さ、むつかしさは時間だけではないはずです。（面倒くさいと思いながらも意地になって解きました。）
ゲームとしての面白さは別にして、人の手で解くことのできるギリギリのところはどこらあたりにあるのかを探ることを目的にしているのかもしれません。でも渡辺氏の初めの問題（問題C）は「どうだ人の手では解けないだろう！」という形で発表されているのですから「人の手では解けない問題を作る」ことを目指しているようにも見えます。そうであればもはや数独ではありません。数独から派生した数学の問題だということになります。
そうであれば「むつかしい」の概念規定が重要になります。「むつかしい」というのは解く立場があってのことです。
たとえば初期設定の数字の数Noについて、「唯一解の存在する最低のNoは？」という問題は数学的に設定することは可能でしょう。でも数独の問題として解くときにNoが小さいことはそのままむつかしいにはつながりません。市販の難問問題集の中にNoが１７，１８というような問題ばかり集めているものがあります。でも別の問題集に載っているNoが２２，２３のものよりも易しいのです。

数独、ナンプレの本を出版している人たちはどういう風に考えているのでしょうか。
２０１０年に発表された問題であれば知れ渡っているはずです。

ゲームとしての数独、ナンプレとは関係がないとして無視しているのでしょうか。

でも数独、ナンプレの内部の話としても「むつかしい」というのは全然吟味されていないように思います。「超難問」とか「究極の難問」、「激辛の難問」とかのタイトルの本がたくさん売られています。むつかしさのレベルはまちまちです。中には鉛筆を縦横に置くだけで解けてしまうような問題まで含まれています。

参考
（B)を解いてみた結果
８１２　７５３　６４９
９４３　６８２　１５７
６７５　４９１　２８３

１５４　２３７　８９６
３６９　８４５　７２１
２８７　１６９　５３４

５２１　９７４　３６８
４３８　５２６　９１７
７９６　２１８　４５２

たぶん間違っていないと思います。
使ったのは紙と鉛筆とマーカーペンだけです。
Ａ４の用紙に書いていけるところまで行きます。
場合分けに入るところからあとはコピーした用紙をたくさん使いました。

どの問題を解くのでも場合分けと仮定が必要です。（Ａ）、（Ｂ）では仮定の積み重ねが必要ですが（Ｄ）では並立的な仮定しか使いません。
一般解法とと言われているものも仮定を使っています。ただ並立的にしか使いません。
「この本の問題を解くのに仮定法は使わない。すべて理詰めで解くことができる」と書いてある本がありますが誤りです。数独、ナンプレの問題の解法は「仮定法」なしでは成り立ちません。

No.5 ベストアンサー 回答者： MagicianKuma 回答日時： 2013/04/09 23:10

将棋の世界ではプロがコンピュータに2連敗したそうな。

詰め将棋の世界でも問題作りにコンピュータが使われている様です。（もっぱら解の検証に）ですが、詰め将棋の難しさやおもしろさまではコンピュータが判断してくれないようです。（今のところ）
実際、詰め将棋界で最も権威のある賞「看寿賞短編部門」を平成元年に取った問題は、なんと3手詰めにもかかわらず、回答者183人中、誤答98人だったそうです。
また、逆に長手数で有名なミクロコスモスは1525手詰みだそうです。これもコンピュータで解けるそうです。問題を作ったのは人間です。それにしても1525手詰みの問題にチャレンジする人がいるのかしらねぇ。おもしろいかどうか・・・
いずれににしても、詰め将棋の世界においては、何らかの名作の基準はあるようです。意外なところに成るとか、合駒に意外性があるとか、初手が奇抜とか。といっても感性の問題ですから明確な定義はあるわけじゃないです。
脳生理学や心理学が進歩すると、難しさやおもしろさといった感情（感性）に関わる領域も数学的にモデル化されるのかもしれませんねぇ。

数独とは詰め将棋は性質が違いますが同じパズルの分野に入るものとして例にあげました。

この回答へのお礼

ありがとうございます。
詰将棋での例、参考になります。

将棋の場合、取った駒を再利用できるというのがチェスとは違うところだと言われています。
数独の場合、手が進むと局面がどんどん狭くなっていきます。
９×９＝８１というという広さの盤というのは将棋と同じなのですが、初期設定の数字が２０個ほどありますからスタート場面での広さは６０ほどです。ここに候補数字が入っています。数独を解くというのはこの候補数字の数を減らしていくという作業です。数字と数字の間に成り立つ位置関係によって候補が制限されていきます。「矛盾を生じない位置関係はどういうものになるか」という判断です。あるセルに入る数字が確定するというのはその結果です。１つの数字が決まると手が進みます。局面が狭くなります。仮定をおいて数字の決まり具合をチェックするという場合でも同じです。際限なく手順が伸びるということは不可能です。（＃３のお礼欄に書きましたが）仮定を積み重ねるとしても１０段ぐらいが限界ではないかと思います。千日手のような堂々巡りは「唯一解が存在する」という条件が置かれていますから出現しません。
二分法で仮定を置いていくのですから、１０段であれば　２^10＝１０２４　の場合が出現すると考えそうですがそうではありません。矛盾に行き当たるまでの仮定の段数のほとんどは１０以下です。２つに分けて数字を入れて手をすすめた時、手の進み方のいい方は、たいてい矛盾に行き着きます。進み方がいいというのは重ねて置かなくてはいけない仮定の入る余裕が少なくなるということだからでしょう。少し進むとすぐに行きづまるという事情があるから仮定の段数が増えていくのです。

渡辺氏に問い合わせてみましたが目標としているのは「仮定の積み重ねの段数を増やすこと」のようです。１つの仮定の中で用いる解法は基本的な定員確定系だけになっているようです。私が感じた「面白くない」ということの理由はこの点にありそうです。仮定の部分を除けば市販の普通の上級問題ぐらいのレベルです。難問とか超難問とかではありません。ただ仮定を積み重ねないと解けないということで解き切るのにものすごく時間がかかるようになっています。同じ論理の作業をただ繰り返すだけですから「面白くない」と感じたのでしょう。
渡辺氏は「手で解けるか、解けないか」とか「人が難しいと感じるか、感じないか」とかは考えていないと言っています。
１０段程度が段数の最大値であればすべて手で解くことができる範囲にあるのではないかと私は考えています。
これはＩｎｋａｒａ氏の８段の問題を解いてみた結果からの予想です。

お礼日時：2013/04/10 12:06

No.4 回答者： alice_44 回答日時： 2013/04/08 09:25

結局、貴方(Inkara氏や渡辺氏ではなく)が、

「むつかしさ」＝「深さ」＝ トラックバックの段数
と考えているのか否か？がハッキリしないし、
貴方の探したいものが、「むつかしさ」の定義なのか
「面白さ」の定式化なのか？も解らない。
貴方自身による「むつかしさ」の定義は、書かないの？

この回答への補足

Ｉｎｋａｒａ氏の新しい問題（２０１３年版とします）と解いてみた結果を載せておきます。
２０１２年版の解答はＩｎｋａｒａ氏のサイトに載っていますが２０１３年版については載っていないようです。

問題（２０１３年）
１００　００７　０９０
０３０　０２０　００８
００９　６００　５００

００５　３００　９００
０１０　０８０　００２
６００　００４　０００

３００　０００　０１０
０４１　０００　００７
００７　０００　３００

解
　２０１２年版に比べると易しそうだというのは問題を見比べてみるだけでもわかるのではないでしょうか。解くのに必要な仮定の積み重ねの段数は２０１２年版が８、２０１３年版が５でした。”ｗｏｒｌｄ’ｓ　ｍｏｓｔ　ｄｉｆｆｉｃｕｌｔ”　という言葉を使うことはできないのです。
（Ｉｎｋａｒａ氏のサイトのｔｏｐ１０には深さが８と書かれています。プログラム（アルゴリズム）に不備がありそうです。）
　　　　
１６２　８５７　４９３
５３４　１２９　６７８
７８９　６４３　５２１

４７５　３１２　９８６
９１３　５８６　７４２
６２８　７９４　１３５

３５６　４７８　２１９
２４１　９３５　８６７
８９７　２６１　３５４

補足日時：2013/04/18 09:10

この回答へのお礼

渡辺氏に問い合わせてみました。
渡辺氏は解に至るまでの手順数の多い問題を作ることを目的にしているようです。仮定の積み重ねがあれば場合の数が増えますから手順の数も多くなります。仮定を置いた後の進め方は基本解法だけに限定しているようです。そうすることによって必要な仮定の数が増えるようにしています。
これが普通の問題の解法とは違うところです。基本解法だけでは解けそうに見えない問題でも特別な数字の配置に着目すると仮定の積み重ねをやるよりは簡単に解くことができるということを解法のポイントにしています。離れたところにある数字の特別な関係が手を進める手掛かりになるということです。でも見つけにくくなっています。仮定を使う場合も並立的です。手順の数を多くするというよりは少なくするほうに関心があるようです。
中には仮定が積み重ねになっているものもありますが仮定の及ぶ範囲が限定されるようになっています。モデュール化されているといってもいいでしょう。

基本解法に限定するというのはそういう約束をするというのではなくて、基本解法しか使えないような局面をプログラム的に作り出しているということのようです。Ｉｎｋａｒａ氏の問題を解いたときには仮定を置いて出てきた局面の中でｘｙ－ｗｉｎｇやｓｗｏｒｄ　ｆｉｓｈのような手筋が表れていないかどうかをチェックしていて時間がかかりました。そういうことは一切考えずに基本解法だけで解いていって、行き詰ったらどんどん仮定を置くというやり方に開き直るとかえって速く解くことができるのです。

ただ、やはり、解く立場を考えずにプログラム的にだけ問題を考えていると手で解けば簡単な問題が、指標的にはむつかしい問題であるという結果になって、こけてしまうということも起こってしまいます。

渡辺氏のサイトからＩｎｋａｒａ氏サイトを開いてみました。ｔｏｐ１０という項目を開くとｗｏｒｌｄ’ｓ　ｍｏｓｔ　ｄｉｆｆｉｃｕｌｔという問題が載っていました。２０１０年、２０１２年の問題とは異なります。たぶん最新版だと考えていいでしょう。そうだとすると２０１２年よりも難しいはずです。Ｉｎｋａｒａ氏の基準に従えば２０１２年の８段を超えているはずだと考えました。ちょっとやってみるのをためらいました。でも紙に書いてＰｅｎｃｉｌ　Ｍａｒｋｓを完成させてみるとそんなに難しいようには見えませんでした。たくさんコピーを用意して仮定を置く作業に取り掛かったのですが５段の仮定で解に行きつきました。「？？？？？・・・」でした。コピーした紙が余ってしまいました。Ｉｎｋａｒａ氏も手を動かして解こうとはしていないようですから判断ミスをやってしまったのかもしれません。

お礼日時：2013/04/10 17:42

No.3 回答者： alice_44 回答日時： 2013/04/05 19:43

発表された「むつかしい」を批判しているよりも、

それを「易しい」と評価するのであれば、自分の「むつかしい」を
まづ定義してみることが建設的かなあ…と。

トラックバック愛好者ではない、数学ファンより。

この回答へのお礼

ありがとうございます。

数独、ナンプレは仮定を積み重ねていけば解けることはわかっています。
でも、私がふだんやっているときには仮定の積み重ねはやりません。
面白くないのです。

仮定を置くことなしには数独を解くことができません。一段の仮定は使います。

Ｉｎｋａｒａ　氏の問題（Ｂ）は一段の仮定では何らの結論も得られないようになっています。分岐を繰り返して枝の一つずつをチェックするしかありません。徹底しています。
私がやった時、８段の仮定の積み重ねで解に行き着きました。渡辺氏のサイトに「深さ」が８となっているのに対応すると思います。でも難易度の指標になるのは「深さ」ではなくて「幅」であるとも書かれています。手でやる場合は「深さ」だけを指標にしても十分だと思います。

仮定の積み重ねの段数を増やしてむつかしさの程度を上げるというのは数独としての面白さとは関係のないことだろうと思います。ただ、問題として成立する限界を探るというだけの意味しかないでしょう。でも、唯一解が存在するという条件で　９×９＝８１　の盤面の上で作るのですから上限が存在するでしょう。可能だとしても１０段ぐらいがせいぜいではないでしょうか。
※もしかしたら、Ｉｎｋａｒａ氏の深さ８が上限になっているのかもしれません。
※※渡辺氏の初めの問題は深さが１０になっていました。しかし、仮定の並列でわかることまで積み重ねの段の一つに組み入れてカウントしてしまっているのでおかしくなってしまったのです。手でやれば簡単に解くことができるというのは一段の仮定が並立的に使われているだけだからです。

お礼日時：2013/04/06 10:00

No.2 回答者： MagicianKuma 回答日時： 2013/04/05 16:17

質問と思われるのは次の2点？

＞「世界で一番むつかしい問題」を作ろうとしている意味とはどういうものでしょう。
渡辺氏に聞くのが早いでしょう。想像するに「そこに山があるから。」位のことでは？

＞数独、ナンプレの本を出版している人たちはどういう風に考えているのでしょうか。
これも関係者に聞くしかない。想像するに、「話題作りになるので大いに結構。」位のことでは？

数独　一ファンより。

この回答へのお礼

ありがとうございます。
＞想像するに「そこに山があるから。」位のことでは？

渡辺氏の場合、「エベレストに上るといって出かけて富士山に上って帰ってきた」というレベルなのではないでしょうか。もしかしたら、駿河の富士ではなくて、近江の富士だったのかもしれません。

研究用のコンピュータを２４時間も動かして、・・・
あきれました。

昔、私が学生だった頃、大学の計算センターの使用料が１分間２００円でした。大卒の初任給が２万円ぐらいの時です。

お礼日時：2013/04/06 06:32

No.1 回答者： fumiuchip 回答日時： 2013/04/05 15:08

そうですか。

お疲れ様です。