問題タブ [sudoku]

この質問のポイントは、乱暴に遅くない最短の数独ソルバーを作成することです。これは次のように定義されています:ボード上に 1 桁しかない可能性があるスポットがある場合は再帰しないでください。

これは私がこれまでPythonで持っていた最短のものです:

コマンドライン入力の一部として使用する最後の行は、次のように変更できます。

これは、不必要な再帰を排除したいという点を除けば、他の数独ゴルフ チャレンジと似ています。どの言語でも構いません。チャレンジ開始！

数独構成が有効かどうかを確認する簡単なアルゴリズムを知っている人はいますか? 私が思いついた最も単純なアルゴリズムは、(サイズ n のボードの場合) Pseudocode です。

しかし、より優れた (よりエレガントなという意味での) 解決策があるに違いないと確信しています。効率はまったく重要ではありません。

特定の数独パズルを解くアルゴリズムを PHP で作成しています。Square9x9 ボード上の個々のタイルごとのクラスと、ボードを表す s のSudokuマトリックスを持つクラスの 2 つのクラスを使用して、ややオブジェクト指向の実装をセットアップしました。Square

私が使用しているアルゴリズムの実装は、一種の 3 層アプローチです。最初のステップは、最も基本的なパズルのみを解決します (ただし、最も効率的です)。ボードの初期設定に基づいて単一の値しか取り得ない正方形を埋め、残りの部分に応じて制約を調整します。未解決の正方形。

通常、この「一定の伝播」のプロセスはボードを完全には解決しませんが、かなりの部分を解決します。次に、2 番目の層が開始されます。これは、未解決の各正方形の「可能な」値について、各ユニット (または行または列などの一意の番号割り当てが必要な 9 つの正方形) を解析します。Squareこの可能な値のリストは、クラスの文字列として表されます。

(上記の第 2 層で説明したように) ユニット内の未解決の正方形の配列全体が与えられると、第 2 層は「可能性」のすべての文字列を単一の文字列に連結します。次に、その単一の文字列を検索して、一意の文字値 (繰り返されない値) を探します。これは、正方形の単位内で、その特定の値を取ることができる正方形が 1 つしかないことを示します。

私の質問は、この第 2 層を実装するために、ユニット内のすべての可能な値のこの文字列を解析し、一意の値を簡単に検出するにはどうすればよいですか? 各インデックスが 1 ～ 9 の数字で表される配列を作成できることはわかっています。また、見つかったその数字の可能な値ごとに、対応するインデックスの値を 1 ずつ増やしてから、配列を再度スキャンして、値は 1 ですが、これは非常に非効率的で、各ユニットに対して配列の 2 つの線形スキャンが必要であり、数独パズルでは 27 個のユニットがあります。

Java (おそらく Python) で数独ソルバー プログラムを作成しようとしています。これをどのように構築すればよいか悩んでいます...

クラスを作成し、各ボックスをそのクラスのオブジェクト (9x9=81 オブジェクト) にしますか? はいの場合、すべてのオブジェクトを制御するにはどうすればよいですか? つまり、クラス内の特定のメソッドをすべてのオブジェクトに呼び出させるにはどうすればよいでしょうか?

多次元配列のようなものを使用して、そこにあるすべての数値を計算して制御する関数を作成するだけですか?

実際、複数の関数を作成できたとしても、各ボックスをオブジェクトにするとしたら、どのようにすべてのオブジェクトを制御するのでしょうか?

ありがとう。

81 個の要素 (9x9 グリッドを表すことを意味する) の配列が与えられた場合、どのように各要素を調べて、その周囲の 3 つを取得し、それらに対して操作を実行してから、各行、列、またはサブマトリックスの次の 3 つに進むことができますか。下または数独グリッドを見て、レイアウトを確認します。

たとえば、私は

と

合計 9x9 グリッドは次のカテゴリの 9 つに分割できるため、各配列には 9 つの要素があり、各列 (x 軸) の要素を 3 つのグループに分けて実行したいと考えています。

それらに対して、結果の 3 つの数値を取得し、それらに対して実行してから、配列に格納します。

これが不可能に聞こえる場合は、申し訳ありませんが、これを行う別の方法が必要です。間違いなく提案を受け入れます...

指定された 9 要素の配列に繰り返し番号 1、2、3、...、9 が含まれていないことを確認する 1 つのライナー (またはそれに近い) が必要です。ゼロの繰り返しはカウントされません (空のセルを表します)。

これまでに出てきた最高のものは次のとおりです。

私の問題を解決したくない場合:)、少なくとも上記のアルゴリズムが正しく機能するかどうかを教えていただけますか?

そして、はい、これを読んだことがあります。

A-star は、グラフの開始ノードと終了ノードの間の最短経路を見つけるために使用されます。ターゲットの状態が具体的に知られておらず、代わりにターゲットの状態の基準しかない場合、何かを解決するためにどのアルゴリズムが使用されますか?

たとえば、Astar のようなアルゴリズムで数独パズルを解くことはできますか? 最終状態がどのように見えるか (どの数字がどこにあるか) はわかりませんが、数独のルール (勝利状態の基準) は知っています。したがって、開始ノードと終了ノードの基準だけがあります。どのアルゴリズムを使用すればよいですか?

与えられたパズルのすべての解を見つける、マルチスレッドの数独ソルバーを作成するという宿題があります。私は以前、非常に高速なシングル スレッドのバックトラッキング数独ソルバーを作成したことがあるので、数独を解く面での助けは必要ありません。

私の問題はおそらく同時実行性を実際に理解していないことに関連していますが、この問題がマルチスレッドからどのように恩恵を受けるかわかりません。パズルの複数のコピーを維持せずに、同じ問題に対して同時に異なる解決策を見つける方法がわかりません。この仮定を考えると (それが間違っていることを証明してください)、マルチスレッド ソリューションがシングル スレッドよりも効率的であるとは思えません。

アルゴリズムの最初の提案を誰かに教えていただければ幸いです（コードなしでお願いします...）

言い忘れていましたが、使用するスレッドの数はプログラムの引数として指定されているので、私が知る限り、パズルの状態とはまったく関係がありません...

また、一意の解決策がない場合もあります。有効な入力は完全に空のボードである可能性があります。それらの1つを報告min(1000, number of solutions)して表示する必要があります（存在する場合）