アカウント名:
パスワード:
解が存在する場合、解が唯一に決まらないという意味でいいんですよね。
読み間違いかもしれませんが、ちょっと変な気がします。
リンク先の記事に、
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
natureの記事の例題が、「解ける問題の例」ではなく「17個のヒントとはこんなもの」という説明の図でしかないと思う。
ちなみに、数独でいま分かっている最小ヒントの問題例って、17個だったっけ？
今回証明された問題が「解が一意になるためには最低 17個のヒントが必要」という意味ならば、「16個以下のヒントでは常に複数解が存在する」ことを証明したという意味でもあると理解しています。
もしそうなら、17個のヒントで複数の解が存在するものを添えて投稿するというのは、ちょっとひどい気がします。
文章見る限り，「17個のヒントで解が一意に決まるものの例」として出ているようですが．#2078731 [srad.jp]のコメントで指摘されている位置の間違いを正しても解が複数出るのでしょうか？
#2078731のコメントで指摘されている位置の間違いを正しても解が複数出るのでしょうか？
すみません、この間違いが見つからないでいるのですが。
数独の解読プログラムはかなりたくさんあるようですが、全部の解を出すのはあまりないのでしょうか。
舌足らずですみません。Natureの記事が間違ってるようでして、リンクされているPDFファイルの方ではどうでしょうか。
> 全部の解を出すのはあまりないのでしょうか。数独って理詰めで唯一解が出せないと意味がないと思いますので（少なくともニコリ的にはその基準で出してるはず）一つの解にたどり着くか、たどり着けないか、それで十分なのかもしれません。極論すると、数字が一つしか入ってない問題は、ニコリの数独的には解なし（問題が間違っている）なんじゃないかなぁ。
失礼しました。Nature が間違っているとは…。確認したところ、PDF の論文中のものは、解が一つしかありませんでした。
ほんとだ、natureサイトの方が間違えている.....(#2078795) とあわせて、これでタイトバウンドですね。
右上の4と3の位置が間違ってるかと。
問題の入力ミスってことですね。
#いや、最初「間違ってる」の意味がよく解らなかったので。
すんません、眠かったので適当でした。「Nature記事」の数字で検証したようですが、元（だと思う）のPDFとその記事の数独が違ってるんですよね。ですから、間違ってるのはNatureの記事だと思います。検証してませんけどｗ
でしょうね。
...うーんコンピュータ使うのはいいけど、力技くさいなぁ。
# 四色問題は、まず状態を分析して場合わけしてからコンピュータだったんだが...
統一的な記述はできなかったのかな?
こういう複雑な場合わけ系が力技なのはある種当然のような気がする。今まで計算が簡単な奴しか「数学」扱いされてなかっただけで。
歴史を振り返れば、無理数をなんとか有理数で表現しようとしていた人もいた。結局のところ、数学的には面白くもなんともないけど、一見簡単に見えて、実は複雑で、しかも解もちゃんと存在する、ってのはこれからどんどん増えてくるんじゃないかな。
やっぱまあそうですよね...
戯言でした、捨ておいてくだされ。
コメ主ではないですが、数学的な解法として違和感を感じるのは、最終的に力技となるとしたって、そこに至るまでに、どれだけ数学的というか論理的な過程を経たのかなという点なのです。単に力技で押し切りましただけでは、いくら結論がすばらしくても他に応用できないので、評価は低くなると思うんですよね。
先に、無理数を有理数で近似するということが述べられていましたが、これは結構複雑な理論を駆使した上で数値計算を行なっているので、今回と同列に並べられないと思います。
何の応用もできなさそうな理論研究なんていくらでもあるんじゃないのか。単に好き嫌いの問題だと思うが。
数学研究者はただ好きなことして遊んでれば良い未来の物理学者が理論を作って未来の工学屋さんが応用してくれるからって数学の学者さんが言ってました
工学屋の先に実業屋がいてその先に虚業をやってる人たちがいるけれど、問題は一流の数学者の給料が三流の株屋の給料よりもはるかに少ないということくらいかな。
数学者が複雑なことに取り組み始めれば、囲碁・チェス・将棋なんかも数学者がやることになりますね
力技といっても、もちろんある程度論理で制限してからのしらみつぶし。すべて数え上げていたら、700万時間ぽっちじゃ解けません。
まぁ、「力技の力を減らす」的な研究も、結構よくあるテーマだったりするので……今回もそういう工夫によって、真っ向からの力技では太刀打ちできないような問題を、現実的な（？）時間内で解けるようにした、というところが大きいようですし。
最低限矛盾なく17箇所埋めれば、てきとうに数字を配置しても問題として成立するんでしょうか？
#苦手なもんで、解けたことない
逆に言えば, 16箇所以下しか数字が埋められていなければ, 絶対に一意な答えが得られないということです.
#2078950が馬鹿だとか言うつもりはないんだけど、その褒め方は無理矢理過ぎるんじゃないかね
345 126 789678 349 125ab9 578 346 cd3 457 698456 891 237897 263 451 531 682 974764 935 812982 714 563
a,b,c,dの4つの空欄のみがあいた(77ヶ所埋め)問題です。この問題は(a, d) = 1, (b, c) = 2 と (a, d) = 2, (b, c) = 1の2種類の解を持つため、問題として成立しません。
また、空欄が3つ以下だと、解が一意に定まることは、理解できるでしょう。ゆえに、問題が複数の解を持ち得ないための十分条件は、78カ所です。
つ「少なくとも」
http://www.nikkei-science.com/page/magazine/0609/sudoku.html [nikkei-science.com]
日経サイエンスのこの記事を昔、読みました。内容は殆ど忘却の彼方ですが当時は予想とされていた17が証明されたんじゃないですかね。ただ、16のとき解が一意になる問題が存在し得ないかというのは証明されたかどうかはっきりしないですけど。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
物事のやり方は一つではない -- Perlな人
「問題として成立しない」が意味不明ですが (スコア: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のとき解が一意になる問題が存在し得ないかというのは証明されたかどうか
はっきりしないですけど。