「数独、少なくとも17カ所埋められていないと問題として成立しない」記事へのコメント

「問題として成立しない」が意味不明ですが

[Anonymous Coward]

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

Re:

[ogino (1668)]

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

リンク先の記事に、

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

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

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

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

例えば：

Re:

[new release (37404)]

natureの記事の例題が、「解ける問題の例」ではなく
「17個のヒントとはこんなもの」という説明の図でしかないと思う。

ちなみに、数独でいま分かっている最小ヒントの問題例って、17個だったっけ？

Re:

[ogino (1668)]

今回証明された問題が「解が一意になるためには最低 17個のヒントが必要」という意味ならば、「16個以下のヒントでは常に複数解が存在する」ことを証明したという意味でもあると理解しています。

もしそうなら、17個のヒントで複数の解が存在するものを添えて投稿するというのは、ちょっとひどい気がします。

Re:

[phason (22006)]

文章見る限り，「17個のヒントで解が一意に決まるものの例」として出ているようですが．
#2078731 [srad.jp]のコメントで指摘されている位置の間違いを正しても解が複数出るのでしょうか？

Re:

[ogino (1668)]

#2078731のコメントで指摘されている位置の間違いを正しても解が複数出るのでしょうか？

すみません、この間違いが見つからないでいるのですが。

数独の解読プログラムはかなりたくさんあるようですが、全部の解を出すのはあまりないのでしょうか。

Re:

[Anonymous Coward]

舌足らずですみません。
Natureの記事が間違ってるようでして、
リンクされているPDFファイルの方ではどうでしょうか。

> 全部の解を出すのはあまりないのでしょうか。
数独って理詰めで唯一解が出せないと意味がないと思いますので
（少なくともニコリ的にはその基準で出してるはず）
一つの解にたどり着くか、たどり着けないか、それで十分なのかもしれません。
極論すると、数字が一つしか入ってない問題は、
ニコリの数独的には解なし（問題が間違っている）なんじゃないかなぁ。

Re:「問題として成立しない」が意味不明ですが

[ogino (1668)]

失礼しました。Nature が間違っているとは…。確認したところ、PDF の論文中のものは、解が一つしかありませんでした。

Re:「問題として成立しない」が意味不明ですが

[new release (37404)]

ほんとだ、natureサイトの方が間違えている.....
(#2078795) とあわせて、これでタイトバウンドですね。