danceman 曰く、アイルランドの数学者が、「数独」が問題として成立するためには9×9のマスのうち少なくとも17箇所が埋められている必要があることを突き止めたとのこと（本家/.、Nature記事）。University College DublinのMcGuire氏は、複雑なアルゴリズムを活用し2年間かけてこの数独の謎を解明したという。スーパーコンピューターの演算処理に要した時間は700万CPU時間にも及んだとのこと。新聞などで出題される数独の問題は通常25箇所ほどマスが埋められており、ヒントが少なくなるほどに問題の難易度が上がるのだそうだ。
最も難しい問題 (スコア:3)
数学のエキスパートが3ヶ月かけて作成した「世界一難しい数独」 [gigazine.net]が23箇所でしたが、
次から最も難しい問題を作る場合、最初から17箇所と分かっているので簡単（？）ですね。
実際、既に作られている [gigazine.net]ようです。
ちょっと見てみたいかも。解けないだろうけど。。。
Re:最も難しい問題 (スコア:1)
必ずしも埋まってる数が少なければ少ないほど難しいとは限らない気がするけど、17カ所にするともっと難しい問題ができるんだろうか?
# そもそも、その問題が本当に「世界一難しい」のかは謎だが。
1を聞いて0を知れ!
Re: (スコア:0)
解ける解けないで言えば、
ひたすら再帰的に掘ってみてダメなら戻ってまた掘ってみて、
を繰り返すだけなので
時間をどれだけつっこむかだけなんですけどね。
Re: (スコア:0)
「ナンプレ」ではなく、「数独」の問題に限定すれば、全部理詰めのみ（仮置きして矛盾が出たら最初の仮定候補を消してリトライ）で解けるはずらしいですけどね。
（商標を持ってるニコリの方針らしい）
Re:最も難しい問題 (スコア:1)
仮定法はニコリのパズル的には理詰めの範疇ではありません
まぁ一つの仮定を置いて脳内でこねくってなんとかなるレベルのものは許容されますが、極力仮定法無しで解けるようにというのが方針の筈
Re: (スコア:0)
元ACです。
理詰めの説明になぜか仮定法の説明を書いてしまいました。
多分もとの
の後に「などを使わない」
って書きたかったのではないかと。
Re: (スコア:0)
たしか、数独をクリアするアプリというのがあった気がする。
人間が頭を悩ませる間もなく、一瞬で解けるようだ・・・すごい虚しい。
Re: (スコア:0)
検索してみれば、javascriptでもそういう実装はいろいろ見つかりますよ。「javascript 数独」でどうぞ。
おそらく比較的簡単な問題しか解けないとは思いますが。
Re:最も難しい問題 (スコア:1)
リンク先とは一切関係ないし、広告になってしまうので
紹介するのはいささか心苦しくもあるのだが、このシート [ecken.co.jp]が良くできてると思う。
元コメの「世界一難しい数独」もきちんと解答を示し、確か「難解」と判定された筈。
個人的には、解が一意に決まらない問題は数独と認めてはいないけれど、
そのような問題でも複数の解をすべて示してくれるのも、便利な機能だとは思う。
Re:最も難しい問題 (スコア:1)
パズルを作るときに問題になるのが、複数解になっちゃうのはダメ、というルールなので
結構必要なソフトですね。
数独ばっかりもてはやされるけど、スリザーリンクとか美術館とかも注目されて欲しいなぁ;-)
「問題として成立しない」が意味不明ですが (スコア:0)
解が存在する場合、解が唯一に決まらないという意味でいいんですよね。
Re:「問題として成立しない」が意味不明ですが (スコア:2)
読み間違いかもしれませんが、ちょっと変な気がします。
リンク先の記事に、
とあるので、（解が唯一に決まらないという）その通りに読めますが、おなじページにある図は、キャプションに
とあり、いかにもこれが数独の問題らしくあるにもかかわらず、解が山ほどあるように見えます。昔作った力ずくのプログラムにかけると、解が 9734通り出力されました。入力ミスか、プログラムがバグっているのかも知れませんが…
例えば：
Re:「問題として成立しない」が意味不明ですが (スコア:1)
natureの記事の例題が、「解ける問題の例」ではなく
「17個のヒントとはこんなもの」という説明の図でしかないと思う。
ちなみに、数独でいま分かっている最小ヒントの問題例って、17個だったっけ？
Re:「問題として成立しない」が意味不明ですが (スコア:2)
今回証明された問題が「解が一意になるためには最低 17個のヒントが必要」という意味ならば、「16個以下のヒントでは常に複数解が存在する」ことを証明したという意味でもあると理解しています。
もしそうなら、17個のヒントで複数の解が存在するものを添えて投稿するというのは、ちょっとひどい気がします。
Re:「問題として成立しない」が意味不明ですが (スコア:1)
文章見る限り，「17個のヒントで解が一意に決まるものの例」として出ているようですが．
#2078731 [srad.jp]のコメントで指摘されている位置の間違いを正しても解が複数出るのでしょうか？
Re:「問題として成立しない」が意味不明ですが (スコア:2)
すみません、この間違いが見つからないでいるのですが。
数独の解読プログラムはかなりたくさんあるようですが、全部の解を出すのはあまりないのでしょうか。
Re: (スコア:0)
舌足らずですみません。
Natureの記事が間違ってるようでして、
リンクされているPDFファイルの方ではどうでしょうか。
> 全部の解を出すのはあまりないのでしょうか。
数独って理詰めで唯一解が出せないと意味がないと思いますので
（少なくともニコリ的にはその基準で出してるはず）
一つの解にたどり着くか、たどり着けないか、それで十分なのかもしれません。
極論すると、数字が一つしか入ってない問題は、
ニコリの数独的には解なし（問題が間違っている）なんじゃないかなぁ。
Re:「問題として成立しない」が意味不明ですが (スコア:2)
失礼しました。Nature が間違っているとは…。確認したところ、PDF の論文中のものは、解が一つしかありませんでした。
Re:「問題として成立しない」が意味不明ですが (スコア:1)
ほんとだ、natureサイトの方が間違えている.....
(#2078795) とあわせて、これでタイトバウンドですね。
N=17 問題 (スコア:1)
最少ヒント数の数独 [ara3.net]
Minimum Sudoku [uwa.edu.au]
Re: (スコア:0)
右上の4と3の位置が間違ってるかと。
Re: (スコア:0)
問題の入力ミスってことですね。
#いや、最初「間違ってる」の意味がよく解らなかったので。
Re: (スコア:0)
すんません、眠かったので適当でした。
「Nature記事」の数字で検証したようですが、
元（だと思う）のPDFとその記事の数独が違ってるんですよね。
ですから、間違ってるのはNatureの記事だと思います。
検証してませんけどｗ
Re:「問題として成立しない」が意味不明ですが (スコア:1)
でしょうね。
...うーんコンピュータ使うのはいいけど、力技くさいなぁ。
# 四色問題は、まず状態を分析して場合わけしてからコンピュータだったんだが...
統一的な記述はできなかったのかな?
M-FalconSky (暑いか寒い)
Re: (スコア:0)
こういう複雑な場合わけ系が力技なのはある種当然のような気がする。今まで計算が簡単な奴しか「数学」扱いされてなかっただけで。
歴史を振り返れば、無理数をなんとか有理数で表現しようとしていた人もいた。結局のところ、数学的には面白くもなんともないけど、一見簡単に見えて、実は複雑で、しかも解もちゃんと存在する、ってのはこれからどんどん増えてくるんじゃないかな。
Re:「問題として成立しない」が意味不明ですが (スコア:1)
やっぱまあそうですよね...
戯言でした、捨ておいてくだされ。
M-FalconSky (暑いか寒い)
Re: (スコア:0)
コメ主ではないですが、数学的な解法として違和感を感じるのは、最終的に力技となるとしたって、
そこに至るまでに、どれだけ数学的というか論理的な過程を経たのかなという点なのです。
単に力技で押し切りましただけでは、いくら結論がすばらしくても他に応用できないので、
評価は低くなると思うんですよね。
先に、無理数を有理数で近似するということが述べられていましたが、これは結構複雑な理論を
駆使した上で数値計算を行なっているので、今回と同列に並べられないと思います。
Re: (スコア:0)
何の応用もできなさそうな理論研究なんていくらでもあるんじゃないのか。
単に好き嫌いの問題だと思うが。
Re: (スコア:0)
数学研究者はただ好きなことして遊んでれば良い
未来の物理学者が理論を作って
未来の工学屋さんが応用してくれるから
って数学の学者さんが言ってました
Re: (スコア:0)
工学屋の先に実業屋がいてその先に虚業をやってる人たちがいるけれど、
問題は一流の数学者の給料が三流の株屋の給料よりもはるかに少ないということくらいかな。
Re: (スコア:0)
数学者が複雑なことに取り組み始めれば、
囲碁・チェス・将棋なんかも数学者がやることになりますね
Re: (スコア:0)
力技といっても、もちろんある程度論理で制限してからのしらみつぶし。
すべて数え上げていたら、700万時間ぽっちじゃ解けません。
Re: (スコア:0)
まぁ、「力技の力を減らす」的な研究も、結構よくあるテーマだったりするので……
今回もそういう工夫によって、真っ向からの力技では太刀打ちできないような問題を、
現実的な（？）時間内で解けるようにした、というところが大きいようですし。
Re:「問題として成立しない」が意味不明ですが (スコア:1)
最低限矛盾なく17箇所埋めれば、てきとうに数字を配置しても問題として成立するんでしょうか？
#苦手なもんで、解けたことない
しろうと考え
Re:「問題として成立しない」が意味不明ですが (スコア:1)
逆に言えば, 16箇所以下しか数字が埋められていなければ, 絶対に一意な答えが得られないということです.
Re: (スコア:0)
#2078950が馬鹿だとか言うつもりはないんだけど、その褒め方は無理矢理過ぎるんじゃないかね
Re: (スコア:0)
(16箇所以下は問題として成立しない)
最小で何箇所埋めればいいか、問題が必ず成立するための十分条件については述べていないようです。
# 文末が”ようです”ばかりで、まじめに論文読んでいないのが丸分かりｗ
Re:「問題として成立しない」が意味不明ですが (スコア:2)
a,b,c,dの4つの空欄のみがあいた(77ヶ所埋め)問題です。
この問題は(a, d) = 1, (b, c) = 2 と (a, d) = 2, (b, c) = 1の2種類の解を持つため、問題として成立しません。
また、空欄が3つ以下だと、解が一意に定まることは、理解できるでしょう。
ゆえに、問題が複数の解を持ち得ないための十分条件は、78カ所です。
1を聞いて0を知れ!
Re: (スコア:0)
つ「少なくとも」
Re: (スコア:0)
Re:「問題として成立しない」が意味不明ですが (スコア:1)
http://www.nikkei-science.com/page/magazine/0609/sudoku.html [nikkei-science.com]
日経サイエンスのこの記事を昔、読みました。内容は殆ど忘却の彼方ですが
当時は予想とされていた17が証明されたんじゃないですかね。
ただ、16のとき解が一意になる問題が存在し得ないかというのは証明されたかどうか
はっきりしないですけど。
BOINCでやってたのとはちがうのかな (スコア:0)
これはBOINCでやってたのとはちがうみたいですね。
探せば他にいくらでもあるけど拙作のarbitrary size Sudoku solver in Fortran95 [srad.jp]。
もし桂祐一郎くんがこのニュースを読んでいたら (スコア:0)
唯一解を得られる下界を見つけて欲しいものだ
本質的に異なる盤面の数は5.47G (スコア:0)
天文学的に多いとは言い難いよね。
Re: (スコア:0)
5.47GってSection 4に書いてある数値？
本質的にそこまで減らす方法が味噌なんじゃない？
17と言っても (スコア:0)
１ブロック当たり２つずつくらいで１カ所だけ１つなんでしょうけど、
偏って配置されてるとかで適切に配置されてなければたぶん解けませんね。
Re: (スコア:0)