0

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

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

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

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

ありがとう。

4

8 に答える 8

12

オーバーエンジニアリングしないでください。これは 2 次元配列か、せいぜい 2 次元配列を表す Board クラスです。特定の行/列を計算する関数と、各正方形にアクセスできる関数を用意します。追加の方法を使用して、各サブ 3x3 および行/列が必要な制約に違反していないことを検証できます。

于 2009-01-11T00:05:14.240 に答える
2

9 x 9 の配列と、数字を追加してパターンのエラーを検出するすべての機能を備えた、数独自体に 1 つのクラスを使用します。

パズルを解くために別のクラスが使用されます。

于 2009-01-11T00:06:27.983 に答える
1

楽しみのために、数独グリッドを解くことができる、python での最短のプログラムであると思われるものを次に示します。

def r(a):i=a.find('0') if i<0:print a [m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]or r(a[:i]+m+a[i+1:])for m in`14**7*9`]r(raw_input())

うーん、それは非常に不可解であり、あなたの質問と一致するとは思わないので、このノイズについてお詫び申し上げます:)

いずれにせよ、これらの 173 文字の説明はここにあります。ここにもフランス語での説明があります

于 2009-04-07T13:58:12.663 に答える
1

Python または Java で行う必要がありますか? 私は Python で多くのプログラミングを行っていますが、AMPL や GLPK などの言語を使用して整数プログラムを使用すると、より簡潔に行うことができます。このような問題では、よりエレガントな (そして一般的により効率的) と思います。

これはAMPLにありますが、これがどのように機能するかは確認していません: http://taha.ineg.uark.edu/Sudoku.txt

于 2009-01-11T00:07:04.097 に答える
1

これを行う最も簡単な方法は、ボードを 2D 9x9 配列で表すことです。各行、列、および 3x3 ボックスを個別のオブジェクトとして参照する必要があるため、プリミティブを使用するよりも (Java では) 各セルを String に格納する方が理にかなっています。String を使用すると、同じオブジェクトへの参照を複数のコンテナーに保持できます。

于 2009-01-11T00:08:57.307 に答える
0

おそらく、正方形ごとにボックスがあり、ボックスのコレクションを持ち、ボックスの相互作用のすべてのルールを含み、ゲーム全体を制御するパズル自体を表す別のクラスを持つデザインは、良いデザインになるでしょう。

于 2009-01-11T00:06:23.770 に答える
0

まず、細胞には2種類あるようです。

  • 既知の呼び出し。固定値、選択肢のないもの。

  • 未知の細胞; 単一の最終値に縮小する候補値のセットを持つもの。

第二に、細胞にはいくつかのグループがあります。

  • 各値のセルが 1 つ必要な水平行と垂直列。その制約は、行または列のさまざまなセルから値を削除するために使用されます。

  • 各値のセルが 1 つ必要な 3x3 ブロック。この制約は、ブロック内のさまざまなセルから値を削除するために使用されます。

最後に、全体的なグリッドがあります。これにはいくつかの補完的な見解があります。

  • 81セルです。

  • セルは、3x3 ブロックの 3x3 グリッドにも収集されます。

  • セルも 9 つの列に収集されます。

  • セルも 9 行に収集されます。

そして、ソルバー戦略オブジェクトがあります。

  1. set( range(1,10) )候補値として持つように設定された各 Unknown セル。

  2. 各行、列、および 3x3 ブロック (27 の異なるコレクション) について:

    を。各セルについて:

    • 明確な値がある場合 (既知のセルと未知のセルでは実装が異なります): このグループ内の他のすべてのセルからその値を削除します。

変更が見つからなくなるまで、上記を繰り返す必要があります。

この時点で、解決済み (すべてのセルが明確な値を報告する) か、複数の値を持つセルがいくつかあります。ここで、「機能する」残りの値の組み合わせを見つけるために、洗練されたバックトラッキング ソルバーを使用する必要があります。

于 2009-01-11T00:40:43.530 に答える
0

規則クラスには、81 個の int (0 は空) の 1 次元配列を含むクラスで十分です。ルール クラスはルールを適用します (各行、列、または 3x3 の正方形に重複する数字はありません)。また、81 個の bool の配列があるため、どのセルが固定され、どのセルを解決する必要があるかがわかります。このクラスへのパブリック インターフェイスには、ボードを操作するために必要なすべてのメソッドがあります。

int getCell(int x, int y);
bool setCell(int x, int y, int value);
bool clearCell(int x, int y);
int[] getRow(int x);
int[] getCol(int y);
int[] getSubBox(int x, int y);
void resetPuzzle();
void loadPuzzle(InputStream stream);

次に、ソルバーはこのクラスへのパブリック インターフェイスを使用してパズルを解きます。私が推測するソルバーのクラス構造は、500 万番目の Sudoku ソルバーを作成するためのものです。ヒントをお探しの場合は、後でこの投稿を編集します。

于 2009-01-11T00:49:56.273 に答える