パスワードを忘れた? アカウント作成
7836138 story
数学

「世界で一番難しい数独」の難しい問題 38

ストーリー by hylom
難しい問題を作るのは難しい 部門より
あるAnonymous Coward 曰く、

東京大学の渡辺宙志助教が、スパコンを用いて「世界で一番難しい数独」を作る試みを行っている。この結果、氏が「2013年3月現在、おそらく世界で一番難しい問題」を発表したのだが、実はこれは人間が簡単に解くことができる問題だった模様。

「難易度の定義」は難しいが、数独の解法とされている「Pencil Marks法」や「Recursive Backtracking法」を使い、探索に必要となる深さを難易度の尺度にしたという。が、判定アルゴリズムにミスがあり、難しくない問題を「難しい」と誤判定していた模様。これを修正した「難しい数独」が再度公開されている。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • この手の話題で(たまに)ナンプレファンで話題にするのは「解いてて楽しい問題」を自動生成するアルゴリズムなんですが、この「楽しい問題」っていうのが定義がなかなか難しい。自動生成されたものだと、解いてて確かにつまらない問題っていうのがあって、面白さも数値化できそうな気はするんですけどねー。

    #オフトピだけどID

    --
    LIVE-GON(リベゴン)
    • by parsley (5772) on 2013年03月13日 19時14分 (#2342713) 日記

      難しすぎると途中で挫折。簡単すぎるとつまらない。
      ニコリって本当にすごいと思う。

      --
      Copyright (c) 2001-2014 Parsley, All rights reserved.
      親コメント
    • by Anonymous Coward on 2013年03月14日 1時15分 (#2342940)
      この研究では解法に用いる手段として
      Recursive Backtrackingを採用してしまっているので
      最終的に修正を重ねてでてきた問題が
      解いていて楽しくない問題に出来上がっていますね

      最終的に絞られた候補の中から
      投機的に数値を仮定して解き進めて
      矛盾が出た段階で投機実行時点まで戻る
      (実際といてみたら確かにそうでした)

      という解法を強いられるのでじゃあ計算機で総当りで解くのを
      人間が肩代わりしてるだけじゃねぇか
      という感情に襲われる数独問題の典型だと思います
      親コメント
      • by Anonymous Coward

        それ言ったらパズルなんてみんな基本はそんなもんだぞ。人間は直感で枝刈りできるけど、無意識に似たようなこと
        やってる(パターンを用いた先読み結果の連想キャッシュってのが表現としては近いか?)。
        難しいってのは枝刈りに使えるデータを減らすことだから(安易に決定できなくなるから難しい=その分先読みが必要)。

        投機的に数値を実行してみなきゃいけない、というのも脳内で一度に処理するには組み合わせが膨大すぎるから、
        投機的な判断を下すことで矛盾に突き当たるまでのステップ数を擬似的に減らしてるだけ。当然このラインも個人に
        依存する。だ

        • 楽しさは難しさとかとはちょっと違いますよ。最初に埋められる数字を1から探していってそれが9だと「なんだかなあ」って思う。別に1から埋めるように作る必要はないがかといって9876という順番で埋めるように作る必要もない。ほか、必然的に埋められる場所が1個ずつしか現れないナンプレだと、難しいっていうよりつまらないわけで、解いていく過程での緩急が楽しさに繋がってたりする。

          --
          LIVE-GON(リベゴン)
          親コメント
          • by Anonymous Coward

            申し訳ない、同じように楽しさと難しさはまた別のものであると言うことを言っているつもりでた。
            だから「一番難しい問題を作りました」の結果出てくるものはどのような手法を使って求めた
            にしても「つまらない問題」になると言いたかった。
            # 「楽しい」のは先に書いたとおりギリギリ読み切れるライン、だと思うので人ごとに違う。
            # だからこそ、パズル集では初級とかのランク分けされてるんだと思う。

            ちなみに自分のやり方はその局面ごとに一番埋まっている列や数字など自由度の
            少ないものからトライするので1から順とか考えたことないし、最初に埋まるのが9で
            も「なんだかな」というのはないですね。
            そもそも数字の大小は解放となんの関係もないと思ってますし。

            # もちろん、最初にトライしたからと言って最初に埋まるわけでもない。
            # 列やブロック、数字ごとの盤面状況で重みつけて投機実行ですね。

        • by Anonymous Coward on 2013年03月14日 10時56分 (#2343185)
          >だから、解法の問題では無くて難しいパズルに関する根本的な問題だと思う。解法は何を使っても一緒。
          >難しい数独作りました、ってのはどんな手法で作っても同じ感想を抱くことになると思う。

          これはBack Tracking解法に関しては全く違うと思います
          そこにはパズルとしての超えられない境界が存在します

          現時点で盤上で得られる情報のみをヒントに使用することにより
          最低どこかひとつのマスは一意に数値を決められ
          その謎解きを繰り返しとくことによって
          最終的に盤面の数値をすべて埋められるのは確かに「パズル」ですが

          現時点で盤上で得られる情報ではどのマスも
          一意には数値を埋められない局面が存在し
          そこから先の局面に進むには選択肢の一番少ないマスに対して
          投機的に数値を埋めて無理やり局面を進める必要がある
          というのはパズルではなくただの組み合わせ試行問題で
          「パズル」としての面白さはないと思います

          あなたと私で同じパズルの早解き競争をしました
          結果私が勝ちました勝負の分かれ目は二択投機実行局面で
          たまたま私は正解を先に実行し
          あなたははずれのほうを先に投機実行したからです
          ではつまらんでしょ?
          親コメント
          • by Anonymous Coward

            どうなんだろう。詰め将棋とかだとありがちな状況だと思うんだけど、
            これはパズルに入らないって事かな。
            競争するシチュエーションにおいて出題するには向いてないのかもしれないね。

            ただ、投機実行にしても盤面からの枝刈りとか工夫できる部分もあるから
            つまらないか、と言われるとそれはそれで有りかなぁ、実際高難度の数独
            だとそういう問題にも普通に出会うし。あれはパズルじゃなかったんだろうか?

            次にトライする数値を決めるにも普通に枝刈りするし、そもそも一つしかな
            い状況だと作業になるから自分はむしろおもしろくないんだよね。

            # そもそも回答速度を競争するというのをあまり

            • by Anonymous Coward
              >実際高難度の数独だとそういう問題にも普通に出会うし。あれはパズルじゃなかったんだろうか?

              実際高難易度の問題には存在しますが
              私はあれはパズルとは感じませんね

              >「縦横3x3の3つをチェックすれば必ず1つの数字が判明する」事でそれを繰り返すこと
              >で手戻りなく全部埋まると言うことを意味して、これだと確認作業になるって事ね。
              >自分はこのレベルは機械的にすすめるので特に楽しいって事はないなぁ。

              私はbacktrackingが入った時点で人の手で解いて面白いパズルだとは思わないですね

              http://www.sudokugame.org/solv/
              少なくとも上記の解き方の中で紹介されている手法を複合的に
              • by Anonymous Coward
                去年本家でもタレこまれたときに
                出てきた問題がbacktraking必須だから
                手でやるだけ時間の無駄とか話題になってましたね

                http://games.slashdot.org/comments.pl?sid=2956211&cid=40540437

                I've tried my own sudoku solver on it which puposefuly doesn't do the guessing/backtracking stuff. It didn't solve one single number. So, you might not want to waste time on trying by hand.

                バックトラッキングが必須な時点で
                人の手で解いて面白い問題じゃないよ
                というのは割りと万国共通なようで
            • by Anonymous Coward

              詰め将棋の喩えはかなり近いと思う。

              長くて難しいのが楽しいかと言われると違うと思うし、それでもすごいとは思う。

              問題のヒントが意外なところに隠されていて、それを発見できたときの瞬間の歓びが大きい。

              「これ、ここに気が付くと一気に片付くぞ~」とかね。
              一種のAha体験。

    • by Anonymous Coward

      開始時の配置がきれいな模様になっていたりとか楽しいですよね。

    • by Anonymous Coward

      ナンプレといわれるとやはり違和感があるなぁ。世間的には同じなのかも、いや、国内じゃそっちのほうが知られているのかもしれないが

    • by Anonymous Coward

      全てのパズルに当てはまると思うんだけど、
      「あれ?もしかしてあのピースをはめると全部解けるんじゃないか?」
      というような、難しさの中にある発見、があると楽しさを感じる。

      それを予め用意しておくパズル製作者は天才だと思う。

  • by Andrion (33929) on 2013年03月13日 19時25分 (#2342723) 日記

    問題を作るのは大変・スパコンが必要なんでしょうが、回答はやっぱり簡単ですね。
    昔作った解法プログラムで計算してみたら、サクッと回答が出てきました。
    # そりゃ人が挑戦すると大変でしょうけどね

    答え:
    146285793
    725963814
    398741256
    851634927
    932178645
    467529138
    683492571
    579316482
    214857369

    • by t-nissie (8647) on 2013年03月13日 22時14分 (#2342834) ホームページ 日記

      回答にかかる時間を比較してみた。
      使ったのはこれ [srad.jp](深さ優先探索(Recursive Backtrackingと同じかな)だけで解を全部探すし、遅い)。
      「失敗」というやつがいちばん時間がかかった。
      究極のアルゴリズム 対 究極の難問 を見てみたい。

      $ ./sudoku NoA 9x9 HW1 HW2 HW3 In1 In2
      NoA        0.01478 sec テキトーに作った解がない問題
      9x9        0.02482 sec テキトーに作った解が2つある問題
      HW1        1.62194 sec 渡辺さんのwatanabe2013.png、「失敗」というやつ
      HW2        0.50455 sec 渡辺さんの130312_sudoku.png
      HW3        0.01694 sec 渡辺さんの130313_2_sudoku.png
      In1        0.02448 sec Inkaraさんのやつその1
      In2        0.48298 sec Inkaraさんのやつその2

      --
      love && peace && free_software
      t-nissie
      親コメント
    • by Anonymous Coward

      最近ではGoogle先生が回答してくれます。

      • by Anonymous Coward

        カメラでとれば、解いてくれるものなかったかな

    • by Anonymous Coward

      理詰めで正解だけ確実に埋めていくには大変だけれども、まずは埋めて間違っていたらやり直しみたいな投機実行的なやり方だとあっさりとけるとかなのかなあ。

      • by Anonymous Coward

        回答が1つ問題だと結構あっさり解けますよ

        その方法、次にどの枠を埋めるかって選び方によってずいぶんと時間がかわるんですよ
        その時点の枠で一種類の数字しか置けない枠があればもちろんおくが、
        なければ置ける数字の数が少ない方、同じならどれだけ、周りに影響をあたえられるで選ぶ。(多分)
        (但し、少ない方がいいことが多いけど、そうでない場合もあるようでなかなか難しい。あまり枠選びに時間がけてもね)

        1つも数字が置いてない白紙の問題で全回答を出すってのをすると我がPCでは終わりそうもなかった。

        • by Anonymous Coward

          むしろ一意に解けないものはできそこないではないかと。

  • by Anonymous Coward on 2013年03月13日 18時43分 (#2342693)

    論理型言語のAlloy使って一番難しい問題を簡単に解けたはず

    • by Anonymous Coward
      キミまで題意を誤らなくてもいいんじゃないか
  • by Anonymous Coward on 2013年03月13日 18時54分 (#2342697)

    東大暇そうだね。

    • by firewheel (31280) on 2013年03月13日 22時54分 (#2342864)

      欧米ではチェスプログラムは人工知能研究の一環として認められるけど、
      日本では将棋プログラムはゲームや遊びとしてしか認められず、
      研究として行うのは難しいと聞いたことがある。

      親コメント
      • by Anonymous Coward

        > 欧米ではチェスプログラムは人工知能研究の一環として認められるけど、

        研究者の努力で認めさせただけのことですし、日本でも(たぶん世界のどこでも)事情は同じです

        • by Anonymous Coward

          落としどころ:
          学術研究の応用分野を広げるために、やはり日本も軍隊を持とう(笑)

          • by Anonymous Coward

            手段のためなら目的を選びません。(キリッ)

          • by Anonymous Coward

            >学術研究の応用分野を広げるために、やはり日本も軍隊を持とう(笑)

            どういう部隊をどれくらい編成すると有効か研究するために
            部隊編成、移動、戦闘をシミュレートする物を作ろう!
            # バグのほとんど無い(比較的最近の)大戦略が欲しい・・・

        • by Anonymous Coward

          ご冗談を。
          人の話を聞く人達と、聞かない人達では前提条件が異なります。

          「オレを説得してみろ。説得できれば金を出してやる。」
          「ただし説得されるつもりも、話を聞くつもりもない。そもそもお前の言ってることは難しすぎてよく分からん。」
          こんな状況で説得しろと言われてもねえ?

    • by Anonymous Coward

      黙ってても金降ってくるし

      • by Anonymous Coward

        黙ってるわけじゃないんじゃない? 勢い余って役に立たない研究してるだけで。
        c.f. 業績リスト [u-tokyo.ac.jp]

      • by Anonymous Coward

        黙ってても金が降ってくるポストなら誰だって欲しい。
        壮絶な奪い合いの末に努力で勝ち取ったポストなんじゃないのかな

    • by Anonymous Coward

      そりゃそうだ、才能あるやつは暇なもんだ
      無能なやつほど忙しいフリしてるしな

    • by Anonymous Coward

      リンク先の解説の後半見たら、数独はNP完全問題であるとか、
      スピングラス系との類似性も指摘されているとか色々書いてありますね。

      要は物性物理の手法が応用できるらしいとやってみたら失敗したと。

      最新の数学、物理に密接に関連しているんだと感心したが、同時に
      最近の東大助教は「〜だった件」という言い回しをタイトルに
      使うんだということも分かった。

  • by Anonymous Coward on 2013年03月14日 13時04分 (#2343290)

    ここまで、未踏スーパークリエータにも、物理の詩人にも言及がないスラドに絶望した!

typodupeerror

アレゲは一日にしてならず -- アレゲ研究家

読み込み中...