数独は必ず推測できるものでしょうか？

いまさらですが、数独について教えて下さい。http://www.websudoku.com/というサイトで数独でときどき遊ぶのですが、ごくまれに解けないことがあります。そんな時も、適当に数字を入れてみると、その先に進んだときに矛盾がでてきて、その数字が違っていたとして、そこにまで戻ることで解くことはできます。しかし、この場合、私が見落としているだけで、数学的には必ず解法がある（推測できる）はずなんでしょうか。

No.1 回答者： SortaNerd 回答日時： 2008/04/02 01:13

「解けない」の判断基準がよく分かりません。

「適当に数字を～戻ることで」解いた場合は「解いた」とは言えないということでしょうか?
それは矛盾がすぐに分かるか後で分かるかの違いに過ぎないと思います。
例えば
・適当に1を入れてみた。その時はよかったが後で隣に1が必要になった。矛盾だ。
というのと
・適当に1を入れてみた。隣に1があった。矛盾だ。
というのは本質的に違いはないでしょう。

＞数学的には必ず解法がある（推測できる）はずなんでしょうか
適当に数字を書いただけでは解なしや複数解の問題が簡単にできてしまいます。問題として成り立たせるために唯一解の問題のみを選別していると思います。
ただ、人間が定石に基づいてプレイして解けるかどうかは分かりません。
そもそも定石と言ってもどの程度までを定石というのかの定義がはっきりしませんので、ある人は解けないと思った問題を別の人は定石に基づいて解くこともあるでしょう。

この回答へのお礼

そうですね、確かに後で矛盾が分かるのと、その時点で自分で矛盾が分かるのでは、本質的に同じかも知れませんね。
コンピューターならいくつか先まで読むということができるのかもしれませんが、私にはそのマスに関連することまでしかその時点では分からりません。なんとなく仮に数字を入れてみてという方法が邪道なような気がしてしまって・・・。でもきっとおっしゃるように本質的には矛盾ないように数をうめていくという意味では、同じなんでしょうね。
丁寧に回答を下さってありがとうございました。

お礼日時：2008/04/02 22:32

No.2 ベストアンサー 回答者： age_momo 回答日時： 2008/04/02 06:36

以前、数独を解く時のメモ帳代わりにPCを使っていたのが高じて

PCで数独の自動解答プログラム、さらに高じて自動問題作成プログラムを
作ったことがあります。

問題を作るのには一旦、ランダムな数字を使って表を埋め(つまり、正解を作る)
そこから解答の一意性を確認しながら(要は他の数字を埋めても正解にならないことを確認)
抜ける数字は抜いていくプログラムです。(抜く評価をする位置はランダム)
経験的には推論を入れない解法で数字を入れていける問題を作っても
数字は25-8個程度しか残りません。推論を許して問題を作成させても最高で2回の
推論、21個の数字が残りました。ここで言う推論とは理論的には決められないが
可能性のある数字を仮に入れて矛盾が出れば最後の推論まで戻って別の数字を
入れる動作です。(何の数字も入って無い状態からの解答はこれの連続で作ります）

これまた経験的には適当な数字を入れながら解答の有無、一意性を確認する
よりは一旦、解答を作ったほうが確実でそれなりの問題は作れます。
よって、問題の表記ミス等が無ければ解答は間違いなくあると思います。

ただ、アート的な数字の残し方をしているものは違う方法を採っているかも知れません。
残す部分を先に決めて、解答の有無、一意性が出る数字の埋め方を考えさせる
プログラムも十分、作成可能ですので。ただ、その場合も解答の有無はPCに
確認させているとは思いますので、解答が無いということは無いと思います。

この回答への補足

ご回答いただいてありがとうございます。

ただ、私はそこまで本格的にやっていないので、少し理解が及ばないのですが、もしかすると、私の質問の仕方が悪かったのかも知れないと思います。私がやってみて解けなかった問題というのも、ただ一つの解というのはあったのです。ただ、おっしゃっている推論ということだと思うのですが、それをしないと解けない問題が非常にまれにあったのです。普通は、その列、行、３×３枠内から推測できました。

お手数でなければ、「経験的には推論を入れない解法で数字を入れていける問題を作っても数字は25-8個程度しか残りません・・・」の部分をもう少し素人にも分かるように説明していただけると助かります。問題を作る際、数字がその数だけ残るということでしょうか。

よろしくお願いいたします。

補足日時：2008/04/02 22:50