マルチスレッドは、1 つのスレッドがリソースを待機する必要があり、その間に別のスレッドを実行できる場合に役立ちます。これには、別のスレッドが CPU 作業を続行している間に、I/O 要求またはデータベース アクセスを待機しているスレッドが含まれます。
マルチスレッドは、個々のスレッドを異なる CPU (またはコア) にファームアウトして、完全に同時に実行できる場合にも役立ちますが、通常はデータを共有する必要があるため、まだ競合が発生します。
マルチスレッドの数独ソルバーがシングルスレッドの数独ソルバーよりも効率的である理由がわかりません。単にリソースを待機する必要がないからです。すべてがメモリ内で行われます。
しかし、大学でやった宿題のいくつかを覚えていますが、それも同様に役に立ちませんでした (30 度で 1 マイル、次に 15 度でさらに 1 マイル掘ったときのトンネルの深さを確認する Fortran コード - はい、私はきれいです年 ：-）。重要なのは、それが有用であることではなく、それができることを示すことです。
アルゴリズムに進みます。
私は、基本的に各パスで一連のルールを実行して、別の正方形を作成しようとするシングル スレッド ソルバーを作成しました。サンプル ルールは次のとおりです。行 1 に空いているマスが 1 つしかない場合、その数字は行 1 の他のすべての数字から明らかです。
すべての行、すべての列、すべての 3x3 ミニグリッドに同様のルールがありました。行/列の交差をチェックするルールもありました (たとえば、特定の正方形が行のために 3 または 4 しか含まず、列のために 4 または 7 しか含まない場合、それは 4 でした)。ここでは詳しく説明しませんが、基本的には手動で解決するのと同じ方法です。
実装に同様のルールがあると思われます（ブルートフォース以外に解決する方法は考えられないため、ブルートフォースを使用した場合は希望がありません:-)。
私が提案するのは、各ルールをスレッドに割り当てて、グリッドを共有させることです。各スレッドは独自のルールを実行し、そのルールのみを実行します。
アップデート：
ジョン、あなたの編集に基づいて：
[編集] 言い忘れていましたが、使用するスレッドの数はプログラムの引数として指定されているため、私が知る限り、それはパズルの状態とはまったく関係がありません...
また、一意の解決策がない場合もあります。有効な入力は完全に空のボードである可能性があります。min(1000, 解の数) を報告し、そのうちの 1 つを表示する必要があります (存在する場合)。
先生は、ルールに基づいて分割するのではなく、分岐点 (複数のルールが適用される可能性がある場所) に基づいて分割することを望んでいるようです。
つまり、ソリューションの任意の時点で、2 つ以上の可能な前進がある場合、それぞれの可能性を個別のスレッドに割り当てる必要があります (効率のためにルールを使用しつつ、同時に各可能性をチェックします)。これにより、ボードの競合が発生しないため、同時実行性が向上します (スレッドを個別の CPU/コアで実行できると仮定します)。各スレッドは独自のコピーを取得します。
さらに、スレッドの数を制限しているため、これを実現するにはスレッド プールの魔法を使用する必要があります。
私がお勧めするのは、作業キューと N スレッドを用意することです。メイン スレッドがすべてのワーカー スレッドを開始するとき、ワーク キューは最初は空です。次に、メイン スレッドはパズルの開始状態をワーク キューに入れます。
ワーカー スレッドは、状態がワーク キューに置かれるのを待つだけで、そのうちの 1 つが処理のためにそれを取得します。作業スレッドは、1 つの小さな変更を加えたシングルスレッド ソルバーです。前進する可能性が X 個ある場合 (X > 1)、ワーカーはそれらのうち X-1 個を作業キューに戻し、他の可能性の処理を続行します。
ですから、解決策は 1 つしかないとしましょう (本当の数独 :-)。最初のワーカー スレッドは、フォークを見つけることなく解決策を徐々に減らしていきます。これは、現在の状況とまったく同じです。
しかし、移動 27 で 2 つの可能性 (たとえば、3 または 4 が左上のセルに入る可能性がある) がある場合、スレッドは最初の可能性 (そのセルに 3 を入れる) で別のボードを作成し、それを作業キューに配置します。次に、4 を独自のコピーに入れて続行します。
別のスレッドは、そのセルに 3 があるボードを取り上げて続行します。そうすれば、2 つの可能性を同時に処理する 2 つのスレッドを実行できます。
いずれかのスレッドがそのボードが解決できないと判断すると、そのボードを破棄し、作業キューに戻ってさらに作業を行います。
いずれかのスレッドがそのボードが解決されたと判断すると、それを保存できるメインスレッドに通知し、以前の解決策を上書きするか (最初に見つかった解決策が解決策)、すでに解決策がある場合は破棄します (最後に見つかった解決策が解決策です)。その後、ワーカー スレッドはさらに作業を行うために作業キューに戻ります。いずれの場合も、メイン スレッドは見つかったソリューションの数を増やす必要があります。
すべてのスレッドがアイドル状態でワーク キューが空の場合、main には解決策があるか、ないかのどちらかです。また、ソリューションの数も含まれます。
ワーカーとメイン スレッド間のすべての通信はミューテックスする必要があることに注意してください (質問の情報に基づいてこれを知っていると仮定しています)。