6

はい、これは新しいものではなく、すでに多くの問題が出回っていることは承知していますが (独自のタグさえあります)、Java で Sudoku Solver を作成したいと考えています。効率的。

おそらく、プログラムでこれを行う最も簡単な方法は、大量の for ループを各列と行で解析し、各セルの可能な値を収集してから、1 つの可能性だけでセルを除外することです (数値が 1 つしか含まれていないか、またはパズルが解けるまで、この数字を含む行/列の唯一のセルです)。もちろん、このアクションについて完全に考えると、すべてのプログラマーの心に危険信号が表示されます。

私が探しているのは、可能な限り最も効率的な方法でこの吸盤を解決するための方法論です (あまり多くのコードを含めないようにしてください - 私はその部分を自分で理解したいと思っています)。

可能であれば、数学的アルゴリズムは避けたいと思っています。それらは簡単すぎて、100% 私の仕事ではありません。

誰かが Sudoku パズルを解くための段階的で効率的な思考プロセスを (人間またはコンピュータによって) 提供できれば、私はとても幸せです :)。私は漠然としたものを探しています (それは挑戦です) が、私を始めるのに十分な情報を提供します (完全に迷うことはありません)。

どうもありがとう、

ジャスティアン・マイヤー

編集：

私のコードを見て、私は次のことを考えました: これらの解法状態 (つまり、数独グリッド) を格納する可能性にはどのようなものがあるでしょうか。2D 配列と 3D 配列が思い浮かびます。どれが一番いいでしょうか？2D は表面から管理する方が簡単かもしれませんが、3D 配列は「ボックス」/「ケージ」番号も提供します。

編集：

どうでも。3D 配列を使用します。

4

4 に答える 4

1

私が自分のボードを作成したとき、後戻りせずに一連のルールを使用してすべてのボードを解決できると思いました。人間のプレイヤーを対象としたパズルでさえ、いくつかの仮説を立てなければならない可能性があるため、これは不可能であることが判明しました。

そこで、パズルを解くための基本的な「ルール」を実装することから始め、最後に停止した場所を解決できるように実装する次のルールを見つけようとしました。最終的には総当たり再帰アルゴリズムを追加せざるを得なくなりましたが、ほとんどのパズルは実際にはそれを使用しなくても解けます。

数独ソルバーに関するブログ記事を書きました。「アルゴリズム」セクションを読むだけで、私がどのようにそれを行ったかがよくわかります。

http://www.byteauthor.com/2010/08/sudoku-solver/

于 2010-08-09T22:52:26.027 に答える
1

Android のリファレンス実装が必要な場合は、上記の投稿のアルゴリズムを使用するソリューションを作成しました。

完全なオープンソース コードはこちら: https://github.com/bizz84/SudokuSolver

さらに、このソリューションは数独パズルを Web サーバーから JSON 形式で読み込み、結果をポストバックします。

于 2012-05-24T17:36:10.497 に答える
1

それは、効率をどのように定義するかによって異なります。

各列と行を検索し、各セルの可能な値を収集してから、可能性が 1 つしかないセルを除外するブルート フォース メソッドを使用できます。

複数の可能性のあるセルが残っている場合は、パズルの状態を保存し、可能性が最も少ないセルを選択し、可能性の 1 つを選択して、パズルを解いてみてください。選択した可能性がパズルの矛盾につながる場合は、保存されたパズルの状態を復元し、セルに戻って別の可能性を選択します。選択したセルのどの可能性もパズルを解決しない場合は、可能性が最も少ない次のセルを選択します。パズルを解くまで、残りの可能性とセルを循環します。

パズルを解こうとすると、各列と行を検索し、各セルの可能な値を収集してから、可能性が 1 つしかないセルを除外します。すべてのセルが取り除かれたら、パズルを解いたことになります。

パズルが解かれるまでコードがさまざまな戦略を試みる、論理的/数学的方法を使用できます。「数独戦略」で Google を検索して、さまざまな戦略を確認してください。論理的/数学的方法を使用して、コードはパズルがどのように解決されたかを「説明」できます。

于 2010-07-27T14:06:00.590 に答える
0

Sudoku Problem をSATisfiability problemに還元することを考えるべきです。

この方法では、AI について考える必要がmathematicallyなくなります。logically

段階的な目標は基本的に次のとおりです。

* Find all the constraints that a Sudoku has. (line, column, box).
* Write these constraints as boolean constraints.
* Put all these constraints in a Boolean Satisfiability Problem.
* Run a SAT solver (or write your own ;) ) on this problem.
* Transform the SAT solution into the solution of the initial Sudoku.

これはIvor SpenceによってSAT4Jを使用して行われました。彼の作品の Java アプレットはhttp://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.htmlにあります。

また、SAT4J Web サイトから Java コードを直接ダウンロードして、どのように見えるかを確認することもできます: http://sat4j.org/products.php#sudoku。

そして最後に、この方法の大きな利点は次のとおりです。N*N Sudokus典型的な問題だけでなく9*9、AIにとってはるかに困難な問題を解決できます:)。

于 2015-07-29T14:21:16.317 に答える