問題タブ [sudoku]

ここで見た最後の質問: Sudoku - Region testing で、3x3 領域を確認する方法を尋ねたところ、誰かが満足のいく答えを得ることができました (ただし、希望どおりに機能させるには多くの調整が必要でした。クラス table_t が何であったかは言及しません。)

プロジェクトを終了し、数独ジェネレーターを作成することができましたが、それは不自然な気がします。そして、パズルを生成するために非常に強引なアプローチをとることで、どうにか物事を複雑にしすぎたように感じます.

基本的に私の目標は、9 ～ 3x3 の領域を持つ 9x9 グリッドを作成することです。各行 / 列 / 領域では、1 ～ 9 の数字を 1 回だけ使用する必要があります。

これを解決する方法は、2 次元配列を使用して、一度に 3 行ずつランダムに数字を配置することでした。3行が完了すると、3行、3つの領域、および3番目の位置までの各垂直列がチェックされます。配列がいっぱいになるまで反復すると同じことが行われますが、ランドでいっぱいになっていて、各行/列/領域を複数回チェックしていたため、非常に非効率的でした。

2次元配列以外の任意のタイプのデータ構造でこれを行うための「より簡単な」方法はありますか? 垂直または水平のいずれかをより適切にチェックすることと一致する可能性のある各 3x3 領域をチェックする簡単な方法はありますか? 計算の観点からは、コードのサイズを劇的に肥大化させずに、より効率的に計算を行う方法があまりにも多くありません。

推測せずに伝統的な数独パズルを解くアルゴリズムはありますか?

ここでの推測とは、候補を試して、それがどこまで進むかを確認することを意味し、推測に矛盾が見つかった場合は、推測のステップに戻って別の候補を試すことを意味します。すべての候補が成功せずに使い果たされた場合、前の推測ステップに戻ります (存在する場合、そうでない場合、パズルの証明は無効です)。

EDIT1：返信ありがとうございます。

従来の数独とは、81 ボックスの数独を意味し、その他の制約はありません。解決策が一意であることがわかっているとしましょう。後戻りせずに解決できることを保証できるアルゴリズムはありますか? バックトラックは普遍的なツールであり、私はそれについて何の問題もありませんが、数独を解くために普遍的なツールを使用すると、数独パズルを解読する価値と楽しさが減少します.

人間は、いわゆる「世界一難しい数独」をどのように解くことができるでしょうか? 推測する必要がありますか?

一部の研究者は、あるデータ分析のアルゴリズムがすべての数独を解決できることを偶然発見したと聞きました。それは本当ですか、彼らも推測する必要がありますか?

まず第一に、これは大学の課題であるため、誰かにコードを書いてもらうように頼んでいるわけではありません。正しい方向に向ける必要があるだけです。:)

では、任意のサイズの (解ける) 数独ボードを解くアルゴリズムを作成する必要があります。任意の 9x9 ボードをすばやく (~1ms) 解決できる再帰関数を作成しましたが、解決するのが難しい大きなボード (16x16) を実行すると苦労します.解決しそうにない。簡単な 16x16 のパズルや空白の 16x16 のボードを解くことができるので、問題は寸法ではないと思います.. 問題はアルゴリズムである可能性が高いと思います.

とにかく、これは私のプログラムの基本的なロジックです..

• すべての正方形の可能な値を格納する 3D ベクトルがあります
• 値が正方形に配置されると、周囲の正方形、行、および列の可能な値から削除されます。

次に、私の解決機能は基本的に次のとおりです。

これについて何か非効率的なことはありますか？うまく機能させる方法はありますか？16x16 のボードに非常に時間がかかるのは、ボードの決定木が非常に大きく、あまり埋められていないためだと思います。奇妙なことに、9x9 ボードは非常に速く解けるからです。

アイデアや提案は絶対に素晴らしいでしょう。私が見逃した情報があれば、私にも知らせてください！

数独パズルを解いて解くプログラムを書こうとしています。ただし、次の行で StackOverflow エラーが発生しています。

移動が有効かどうかをチェックする isLegal メソッドがあります。手が有効で、次の手も有効な場合、それをスタックに追加します。それが有効であるが、次の動きが有効でない場合、有効な番号を検索し続ける必要があります。何が原因なのかわからない。

わかりましたので、関数をバックトラッキング関数に変更しました（オンラインで見つけました）。ファイルから読み取って配列に入力しますが、チェック機能は適切に機能しているため、変更していません。以下は、私が解決しようとしているパズルです (ゼロは空のスペースです)。

私は c++ が初めてで、宿題 (数独) をするときに問題が発生しました。

命令は次のように述べています。

私は試しました（それはboard.ccに書かれています）：

エラーメッセージが表示されました:

私も試しました：

これは、コンプ時に問題がありませんでした。しかし、実行中も機能しません。

どうやってするの？ここで本当に助けが必要です、thx！

board.h のコードは次のとおりです。

完全な説明はここにあります: http://www.kth.se/polopoly_fs/1.136980!/Menu/general/column-content/attachment/2-2.pdf

コード: http://www.kth.se/polopoly_fs/1.136981!/Menu/general/column-content/attachment/2-2.zip

I'm new to C++ and have to do a home assignment (sudoku). I'm stuck on a problem.

Problem is that to implement a search function which to solve a sudoku.

Instruction: In order to find a solution recursive search is used as follows. Suppose that there is a not yet assigned field with digits (d1....dn) (n > 1). Then we first try to assign the field to d1, perform propagation, and then continue with search recursively. What can happen is that propagation results in failure (a field becomes empty). In that case search fails and needs to try different digits for one of the fields. As search is recursive, a next digit for the field considered last is tried. If none of the digits lead to a solution, search fails again. This in turn will lead to trying a different digit from the previous field, and so on.

数字dにフィールドを割り当てて試行する前に、現在のボードのコピーである新しいボードを作成する必要があります（コピーコンストラクターを使用して、ヒープからボードをnewで割り当てます）。その後、コピーに対して割り当てを実行します。検索への再帰呼び出しが失敗した場合は、次の桁を試すために新しいボードを作成できます。

私はもう試した：

もう1つの問題は、再帰呼び出しをどこで使用するかです。任意のヒント？どうも！

完全な手順はここにあります：http ：//www.kth.se/polopoly_fs/1.136980！/Menu/general/column-content/attachment/2-2.pdf

コード：http ：//www.kth.se/polopoly_fs/1.136981！/Menu/general/column-content/attachment/2-2.zip

裸のシングルと隠されたシングルのテクニックを使ってそれを解決するために、次の2つのデータ構造のどちらを数独ボードを表すために使用するべきかについて私は躊躇しています。

1.1。

このようにして、セル（row、col）に候補nが含まれているかどうかを確認するには、どちらcandidates[row, col, n]が真か偽かを確認します。

2.2。

このように、セル（r、c）に候補nが含まれているかどうかを確認するには、式row[r, n] && col[c, n] && square3x3[r/3 * 3 + c/3, n]が真か偽かを確認します。

特定のセルが番号nで解決される場合、第1の方法では、特定のセルの行、列、square3x3のすべての3x9セルの候補を更新する必要がありますが、第2の方法では、row [、n]、colのみを設定します。 [、n]およびsquare3x3 [、n]をtrueに設定します。

しかし、裸のシングルと隠されたシングルを見つけるのにどちらの方法が適切かつ効率的かはわかりません。

誰かが私に隠されたシングルを見つけるためのアルゴリズムを提案できますか？

助けてくれてありがとう！

私は C++ の初心者で、プログラミングを始めてまだ数日なので、ばかげているように思えるかもしれませんが、私の配列が正しく動作しない理由を見つけていただけますか? これは、数独パズルを解くために設計しているプログラムの始まりですが、それを解くために使用している 2D 配列が正しく機能していません。

}

また、数独ボードをもっと簡単に組み立てる方法があるかもしれないことは承知していますが、これがどのように機能するかはすでに頭の中にあります。失敗した場合、学習する唯一の方法は失敗することです。私が知りたいのは、配列の何が問題なのかということだけです。

私は頭の上にいるような気がします。私はJavaScriptの数独ゲームを書こうとしています。すべてのコードを投稿する代わりに、ここに私のゲームへのリンクを示します。私の情報源はここにあります今のところ、それはソリューション グリッドを (しようと) 吐き出すだけです。私の問題は、コードが無期限にハングする場合があることです。また、Firefox で 1 秒以内にグリッドを正常に作成する場合もあります。ご協力いただきありがとうございます！