複雑さと問題解決のコースで行うプロジェクトがあり、そのプロジェクトを数独に基づいて行うことにしました。私が行った調査から、数独は (プロジェクトに必要な) NP 完全問題であり、そのためのアルゴリズムを作成するいくつかの方法を見つけました。力ずくで解決する方法を計画していますが、他に 2 つの方法を実行する必要があります。Exact Cover 問題として解く方法などいくつかの方法を見つけました。数独を SAT 問題として説明している論文も見つけました。しかし、私の質問は次のとおりです。数独の証明済みの多項式ソリューションはありますか? 私の先生は、約 5 年前に「上級」紳士による「賢い」解決策があったと思っているようですが、彼が覚えているのはそれだけです。このソリューションが何であるか、または他の多項式ソリューションが何であるかを知っている人はいますか? 私'
ありがとう！
一般化された数独問題 (n 2 × n 2グリッド) は NP 困難であるため、数独パズルを解くための既知の多項式時間アルゴリズムがあれば、P = NP であることが証明されます。それは大きな取引になるでしょう。
心に留めておくべきことは、私たちが知っている数独パズルはすべて 9 × 9 のグリッドであるということです。その結果、数独パズルを解く際の時間の複雑さを測定しようとする場合、big-O 表記法を使用するのは実際には良い考えではありません.固定サイズの数独パズルを解いています。別の言い方をすると、数独パズルを解くための多項式時間について話したい場合は、「どの変数の多項式ですか?」という質問に答える必要があります。常に 9 × 9 の数独グリッドを解く場合、その答えは質問は本当に明確ではありません。
人間のような戦略を使用することもできますが、これは多項式にすることができますが、すべての数独の解決策を見つけることはできません (一意の解決策がある場合でも)。また、数独をグラフの色付けの問題に還元することも非常に簡単です (各セルはグラフのノードで表され、ノードは数独の規則に従って接続され、同じ色を持たないようにします。色）。