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

数独、少なくとも17カ所埋められていないと問題として成立しない 48

ストーリー by hylom
16カ所を埋めた問題を作る嫌がらせが成立する 部門より
danceman 曰く、

アイルランドの数学者が、「数独」が問題として成立するためには9×9のマスのうち少なくとも17箇所が埋められている必要があることを突き止めたとのこと(本家/.Nature記事)。

University College DublinのMcGuire氏は、複雑なアルゴリズムを活用し2年間かけてこの数独の謎を解明したという。スーパーコンピューターの演算処理に要した時間は700万CPU時間にも及んだとのこと。

新聞などで出題される数独の問題は通常25箇所ほどマスが埋められており、ヒントが少なくなるほどに問題の難易度が上がるのだそうだ。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
  • by DesKwa (35996) on 2012年01月10日 23時12分 (#2078669)

    数学のエキスパートが3ヶ月かけて作成した「世界一難しい数独」 [gigazine.net]が23箇所でしたが、
    次から最も難しい問題を作る場合、最初から17箇所と分かっているので簡単(?)ですね。

    実際、既に作られている [gigazine.net]ようです。
    ちょっと見てみたいかも。解けないだろうけど。。。

    • by greentea (17971) on 2012年01月11日 3時50分 (#2078764) 日記

      必ずしも埋まってる数が少なければ少ないほど難しいとは限らない気がするけど、17カ所にするともっと難しい問題ができるんだろうか?
      # そもそも、その問題が本当に「世界一難しい」のかは謎だが。

      --
      1を聞いて0を知れ!
      親コメント
    • by Anonymous Coward

      解ける解けないで言えば、
      ひたすら再帰的に掘ってみてダメなら戻ってまた掘ってみて、
      を繰り返すだけなので
      時間をどれだけつっこむかだけなんですけどね。

      • by Anonymous Coward

        「ナンプレ」ではなく、「数独」の問題に限定すれば、全部理詰めのみ(仮置きして矛盾が出たら最初の仮定候補を消してリトライ)で解けるはずらしいですけどね。
        (商標を持ってるニコリの方針らしい)

        • by Anonymous Coward on 2012年01月11日 21時49分 (#2079178)

          仮定法はニコリのパズル的には理詰めの範疇ではありません
          まぁ一つの仮定を置いて脳内でこねくってなんとかなるレベルのものは許容されますが、極力仮定法無しで解けるようにというのが方針の筈

          親コメント
          • by Anonymous Coward

            元ACです。
            理詰めの説明になぜか仮定法の説明を書いてしまいました。
            多分もとの

            仮置きして矛盾が出たら最初の仮定候補を消してリトライ

            の後に「などを使わない」
            って書きたかったのではないかと。

    • by Anonymous Coward

      たしか、数独をクリアするアプリというのがあった気がする。
      人間が頭を悩ませる間もなく、一瞬で解けるようだ・・・すごい虚しい。

      • by Anonymous Coward

        検索してみれば、javascriptでもそういう実装はいろいろ見つかりますよ。「javascript 数独」でどうぞ。
        おそらく比較的簡単な問題しか解けないとは思いますが。

        • by Anonymous Coward on 2012年01月11日 21時23分 (#2079158)

          リンク先とは一切関係ないし、広告になってしまうので
          紹介するのはいささか心苦しくもあるのだが、このシート [ecken.co.jp]が良くできてると思う。
          元コメの「世界一難しい数独」もきちんと解答を示し、確か「難解」と判定された筈。
          個人的には、解が一意に決まらない問題は数独と認めてはいないけれど、
          そのような問題でも複数の解をすべて示してくれるのも、便利な機能だとは思う。

          親コメント
          • by Rem (17869) on 2012年01月11日 22時18分 (#2079195) 日記

            パズルを作るときに問題になるのが、複数解になっちゃうのはダメ、というルールなので
            結構必要なソフトですね。
            数独ばっかりもてはやされるけど、スリザーリンクとか美術館とかも注目されて欲しいなぁ;-)

            親コメント
  • by Anonymous Coward on 2012年01月10日 22時13分 (#2078624)

    解が存在する場合、解が唯一に決まらないという意味でいいんですよね。

    • 読み間違いかもしれませんが、ちょっと変な気がします。

      リンク先の記事に、

      puzzles with 16 or fewer clues do not have a unique solution.

      とあるので、(解が唯一に決まらないという)その通りに読めますが、おなじページにある図は、キャプションに

      A sudoku puzzle needs at least 17 clues to be solvable.

      とあり、いかにもこれが数独の問題らしくあるにもかかわらず、解が山ほどあるように見えます。昔作った力ずくのプログラムにかけると、解が 9734通り出力されました。入力ミスか、プログラムがバグっているのかも知れませんが…

      例えば:

        2  3  7     8  4  1     5  6  9
        8  9  6     7  2  5     4  3  1
        5  1  4     3  9  6     2  8  7

        3  6  1     5  7  9     8  4  2
        4  7  5     6  8  2     1  9  3
        9  2  8     1  3  4     7  5  6

        6  4  2     9  1  8     3  7  5
        1  5  3     4  6  7     9  2  8
        7  8  9     2  5  3     6  1  4

        3  6  9     8  4  1     7  5  2
        2  8  1     7  9  5     4  3  6
        5  7  4     3  2  6     9  8  1

        1  3  6     5  7  4     8  2  9
        7  9  5     6  8  2     1  4  3
        4  2  8     1  3  9     5  6  7

        6  4  2     9  1  8     3  7  5
        9  5  3     4  6  7     2  1  8
        8  1  7     2  5  3     6  9  4

      親コメント
    • でしょうね。

      ...うーんコンピュータ使うのはいいけど、力技くさいなぁ。

      # 四色問題は、まず状態を分析して場合わけしてからコンピュータだったんだが...

      統一的な記述はできなかったのかな?

      --
      M-FalconSky (暑いか寒い)
      親コメント
      • by Anonymous Coward

        こういう複雑な場合わけ系が力技なのはある種当然のような気がする。今まで計算が簡単な奴しか「数学」扱いされてなかっただけで。

        歴史を振り返れば、無理数をなんとか有理数で表現しようとしていた人もいた。結局のところ、数学的には面白くもなんともないけど、一見簡単に見えて、実は複雑で、しかも解もちゃんと存在する、ってのはこれからどんどん増えてくるんじゃないかな。

        • やっぱまあそうですよね...

          戯言でした、捨ておいてくだされ。

          --
          M-FalconSky (暑いか寒い)
          親コメント
        • by Anonymous Coward

          コメ主ではないですが、数学的な解法として違和感を感じるのは、最終的に力技となるとしたって、
          そこに至るまでに、どれだけ数学的というか論理的な過程を経たのかなという点なのです。
          単に力技で押し切りましただけでは、いくら結論がすばらしくても他に応用できないので、
          評価は低くなると思うんですよね。

          先に、無理数を有理数で近似するということが述べられていましたが、これは結構複雑な理論を
          駆使した上で数値計算を行なっているので、今回と同列に並べられないと思います。

          • by Anonymous Coward

            何の応用もできなさそうな理論研究なんていくらでもあるんじゃないのか。
            単に好き嫌いの問題だと思うが。

          • by Anonymous Coward

            数学研究者はただ好きなことして遊んでれば良い
            未来の物理学者が理論を作って
            未来の工学屋さんが応用してくれるから
            って数学の学者さんが言ってました

            • by Anonymous Coward

              工学屋の先に実業屋がいてその先に虚業をやってる人たちがいるけれど、
              問題は一流の数学者の給料が三流の株屋の給料よりもはるかに少ないということくらいかな。

        • by Anonymous Coward

          数学者が複雑なことに取り組み始めれば、
          囲碁・チェス・将棋なんかも数学者がやることになりますね

      • by Anonymous Coward

        力技といっても、もちろんある程度論理で制限してからのしらみつぶし。
        すべて数え上げていたら、700万時間ぽっちじゃ解けません。

      • by Anonymous Coward

        まぁ、「力技の力を減らす」的な研究も、結構よくあるテーマだったりするので……
        今回もそういう工夫によって、真っ向からの力技では太刀打ちできないような問題を、
        現実的な(?)時間内で解けるようにした、というところが大きいようですし。

    • 最低限矛盾なく17箇所埋めれば、てきとうに数字を配置しても問題として成立するんでしょうか?

      #苦手なもんで、解けたことない

      --
      しろうと考え
      親コメント
      • 逆に言えば, 16箇所以下しか数字が埋められていなければ, 絶対に一意な答えが得られないということです.

        親コメント
      • by Anonymous Coward
        17箇所というのは問題としての必要条件のようです。
        (16箇所以下は問題として成立しない)

        最小で何箇所埋めればいいか、問題が必ず成立するための十分条件については述べていないようです。

        # 文末が”ようです”ばかりで、まじめに論文読んでいないのが丸分かりw
        • 345 126 789
          678 349 125
          ab9 578 346
           
          cd3 457 698
          456 891 237
          897 263 451
           
          531 682 974
          764 935 812
          982 714 563

          a,b,c,dの4つの空欄のみがあいた(77ヶ所埋め)問題です。
          この問題は(a, d) = 1, (b, c) = 2 と (a, d) = 2, (b, c) = 1の2種類の解を持つため、問題として成立しません。

          また、空欄が3つ以下だと、解が一意に定まることは、理解できるでしょう。
          ゆえに、問題が複数の解を持ち得ないための十分条件は、78カ所です。

          --
          1を聞いて0を知れ!
          親コメント
          • by Anonymous Coward

            つ「少なくとも」

            • by Anonymous Coward
              必要条件の話から逸れて十分条件の話をしてるんだから、 そのツッコミは的外れだよ
    • http://www.nikkei-science.com/page/magazine/0609/sudoku.html [nikkei-science.com]

      日経サイエンスのこの記事を昔、読みました。内容は殆ど忘却の彼方ですが
      当時は予想とされていた17が証明されたんじゃないですかね。
      ただ、16のとき解が一意になる問題が存在し得ないかというのは証明されたかどうか
      はっきりしないですけど。

      親コメント
  • by Anonymous Coward on 2012年01月10日 22時52分 (#2078646)

    これはBOINCでやってたのとはちがうみたいですね。
    探せば他にいくらでもあるけど拙作のarbitrary size Sudoku solver in Fortran95 [srad.jp]。

  • by Anonymous Coward on 2012年01月10日 23時39分 (#2078695)

    唯一解を得られる下界を見つけて欲しいものだ

  • by Anonymous Coward on 2012年01月11日 10時14分 (#2078847)

    天文学的に多いとは言い難いよね。

    • by Anonymous Coward

      5.47GってSection 4に書いてある数値?
      本質的にそこまで減らす方法が味噌なんじゃない?

  • by Anonymous Coward on 2012年01月11日 15時10分 (#2079035)

    1ブロック当たり2つずつくらいで1カ所だけ1つなんでしょうけど、
    偏って配置されてるとかで適切に配置されてなければたぶん解けませんね。

    • by Anonymous Coward
      「17個あれば問題として成立することがある」のと「17個あっても問題として成立しないことがある」のは矛盾しませんから。
typodupeerror

最初のバージョンは常に打ち捨てられる。

読み込み中...