私はRubyでKillerSudokuSolverをプログラミングしており、人間の戦略を取り入れてコードに組み込んでいます。私は約10の戦略を実行しましたが、これには問題があります。
サムナンプレには、細胞の「ゾーン」があり、これらの細胞の合計を知っており、各細胞の可能性を知っています。
例 ：
私のプログラムには、可能性を排除するためにすべての可能性を試してもらいたいです。たとえば、ここでは、セル2と3で2つの数値を加算して3を作成できないため、セル1を9にすることはできません。
ですから、いくつものセルに対して、それらを試して、それが機能しないことを確認することによって不可能なセルを削除することを望んでいます。
どうすればこれを機能させることができますか？
ゲーム解決の一般的な問題にアプローチする方法は複数あり、人間の戦略をエミュレートすることが常に最善の方法であるとは限りません。とはいえ、質問を解決する方法は次のとおりです。
第1の方法、ブルートフォース
基本的に、セルの組み合わせのすべての可能性を試して、正しい合計を持つものを選択したいと考えています。
cell_1 = [1,3,4,9]
cell_2 = [2,4,5]
cell_3 = [3,4,9]
all_valid_combinations = cell_1.product(cell_2,cell_3).select {|combo| combo.sum == 12}
# => [[1, 2, 9], [3, 5, 4], [4, 4, 4], [4, 5, 3]]
#.sum isn't a built-in function, it's just used here for convenience
これを個々のセルに切り詰めるには、次のようにします。
cell_1 = all_valid_combinations.map {|combo| combo[0]}.uniq
# => [1, 3, 4]
cell_2 = all_valid_combinations.map {|combo| combo[1]}.uniq
# => [2, 5, 4]
. . .
膨大な数のセルがない場合は、この方法の方がコーディングが簡単です。ただし、少し非効率になる可能性があります。小さな問題の場合、これが私が使用する方法です。
第 2 の方法、バックトラック検索
別のよく知られた手法は、他のアプローチから問題を取り上げます。基本的には、各セルに対して、「他のセルを考えると、このセルはこの数になることができるか?」と尋ねます。
では、セル 1 から始めて、数字は 1 になることができますか? 調べるために、セル 2 と 3 の合計が 11 になるかどうかを確認します。 (12-1) * セル 2 は値 2 を持つことができますか? 確認するには、セル 3 の合計を 9 にすることができます (11-1)
等々。非常に多くの有効な組み合わせを持つことができる非常に大きなケースでは、セルの有効な数値を初めて見つけたときに「true」を返すことができるため、これはわずかに高速になります。ただし、再帰アルゴリズムを理解するのが少し難しいと感じる人もいるため、マイレージは異なる場合があります。