3

基本的に、00 ～ 99 の 2 桁の数字で埋められた 3 x 3 のグリッドがあります。一部の数字は入力として与えられ、残りは不明です。このような問題をCでブルートフォースで解決する方法についての提案は何ですか?

編集：申し訳ありませんが、問題の一部を忘れていました。すべての行と列、および対角線の合計は同じ数になる必要があります。アルゴリズムを使い始めるためのいくつかのアイデアだけで、コードは必要ありません

4

5 に答える 5

4

問題に対する単純な再帰的解決策があります。これは、バックトラッキングと呼ばれるブルート フォースの一種の例です (Google で検索してください)。

再帰関数 (たとえば、fill_next) は、未知の値を持つ次のセルを見つけます。そのようなセルがない場合、正方形が要件に適合するかどうか (合計が正しいかどうか) を確認し、適合する場合はその正方形を解として出力します。その後、戻ります。未知の値を持つセルがある場合、ループし、そのセルに対して 0 から 99 までの各値を順番に試してから、次の未知のセルを埋めるために自分自身を再帰的に呼び出します。

未知の値を持つ次のセルに到達する方法: 次のセルの番号を find_next に渡すだけで、次のセルを調べ始めることができます。fill_next(0) を呼び出すことですべてを開始します。9 個のセルがあるため、セル番号は 0 ～ 8 です。正方形を 2D 配列に格納する場合は、num%3 と num/3 をインデックスとして使用します。

必要な数行のコードを示すだけで、これを説明するのははるかに簡単になりますが、あなたはそれを望まないと言いました。

于 2011-02-08T00:10:58.163 に答える
4

魔方陣は、実際には (単純な) 連立方程式のシステムです。行列に変換し、ガウス消去法を使用してこれらを解決します。これは力ずくでありながら、同時にかなりエレガントです。解決策が一意でない場合は、少なくとも解決策が何であるかについての制約のセットが減り、解決策がはるかに簡単になります。

于 2011-02-08T14:45:27.043 に答える
1

あなたの問題は何ですか？それぞれの数字が何であるかを調べようとしていますか? 数字が満たさなければならない基準はありますか？もしそうなら、それぞれの可能な数字を推測してください?? 組み合わせが基準に適合するまでスポットします。

于 2011-02-07T23:13:54.983 に答える
0

魔方陣問題のブルート フォースは非常に簡単です。

  1. 各行を反復し、各行の合計を計算します (i 定数、j++ を保持) (3 つの合計)
  2. 各列を反復処理し、各列の合計を計算します (j 定数、i++ を保持) (3 つの合計)
  3. 両方の対角線を反復し、合計を計算します (i++、j++、i が j に等しい) (2 つの合計)

ある時点で合計が最初に計算した合計と同じでない場合は、完了です。すべての合計が等しい場合、魔方陣が見つかりました。

于 2011-02-07T23:30:09.867 に答える
0

3x3 グリッドは 2 次元配列のように聞こえます。

JS のコード例:

var a=[
    [ 11, 12, 13 ],
    [ 21, 22, 23 ],
    [ 31, 32, 33 ]
];
for(var r=0; r<a.length; r++)
    for(var c=0; c<a[r].length; c++)
        console.log(r+','+c+' = '+a[r]+','+a[r][c]);

a - 3x3 グリッド配列 (配列の配列) r - 現在の行の反復 c - 現在の列の反復

オプションで、a.length両方a[r].lengthとも3の定数にすることができます（あなたの場合）。

于 2011-02-07T23:18:16.210 に答える