1

低レベルのコースで課題として再帰を扱うのは初めてです。私はインターネットを見回しましたが、私が思いついた方法と同様の方法を使用している人を見つけることができないようです (おそらく、これが機能しない理由について何かを示しています)。std::__copy_move...エラーは、c++ STL にあると思われるセグメンテーション違反です。とにかく、私のコードは次のとおりです。

bool sudoku::valid(int x, int y, int value)
{
    if (x < 0) {cerr << "No valid values exist./n";}

    if (binary_search(row(x).begin(), row(x).end(), value))
        {return false;}                 //if found in row x, exit, otherwise:
    else if (binary_search(col(y).begin(), col(y).end(), value))
        {return false;}                 //if found in col y, exit, otherwise:
    else if (binary_search(box((x/3), (y/3)).begin(), box((x/3), (y/3)).end(), value))
        {return false;}                 //if found in box x,y, exit, otherwise:
    else
        {return true;}                  //the value is valid at this index
}

int sudoku::setval(int x, int y, int val)
{
    if (y < 0 && x > 0) {x--; y = 9;}   //if y gets decremented past 0 go to previous row.
    if (y > 8) {y %= 9; x++;}           //if y get incremented past 8 go to next row.

    if (x == 9) {return 0;}             //base case, puzzle done.
    else {
        if (valid(x,y,val)){            //if the input is valid
            matrix[x][y] = val;         //set the element equal to val
            setval(x,y++,val);          //go to next element
        }
        else {
            setval(x,y,val++);          //otherwise increment val
            if(val > 9) {val = value(x,y--); setval(x,y--,val++); }
        }                               //if val gets above 9, set val to prev element,  
    }                                   //and increment the last element until valid and start over
}

私はしばらくの間、このことに頭を悩ませようとしてきましたが、何が問題なのか理解できないようです. どんな提案でも大歓迎です！:)

4

5 に答える 5

1

sudoku::setvalを返すはずですが、int何も返さないパスが少なくとも 2 つあります。そうしないと、ランダムな未定義の動作が発生するため、他のパスで何を返す必要があるかを理解する必要があります。

于 2011-10-24T14:33:04.580 に答える
1

これ以上の情報がなければ、それを伝えることは不可能です。たとえば、関連するデータ構造や、何rowをcol返すかなどです。それでも、明らかな問題がいくつかあります。

  • ではsudoku::valid、明らかにエラー状態 ( ) をチェックしますが、返されx < 0ません。の負の値を使用して、テストを続行しますx。

  • また、ソートされた値への参照をsudoku:valid実行rowしてcol実際に返しますか? 値がソートされていない場合、binary_search未定義の動作が発生します (ソートされている場合、名前は誤解を招く可能性があります)。そして、それらが同じオブジェクトへの参照ではなく、値 (何かのコピー) を返す場合、関数begin()とend() 関数は別のオブジェクトを参照することになり、これも未定義の動作です。

  • 最後に、あなたのアルゴリズムには後戻りが見られず、それがどのように解決に進むかわかりません。

FWIW: 同様のことを書いたとき、ボードに 81 個の要素の単純な配列を使用し、インデックス (0 ～ 80) を適切な行、列、およびボックスにマップする静的配列を作成しました。そして、9 つの行、列、およびボックスのそれぞれについて、使用した値のセット (ビットマップ) を保持しました。これにより、合法性のチェックが非常に簡単になり、インデックスをインクリメントするだけでテストする次の正方形にインクリメントできることを意味しました。結果のコードは非常に単純でした。

sudoku使用するデータ表現とは無関係に、以下が必要になります。解を見つけたかどうかを知るための「グローバル」(おそらく のメンバー) 手段。正方形の 9 つの可能な値のそれぞれを試すループ (解が見つかったときに停止) と、再帰。私が行ったように、ボードに単純な配列を使用していない場合は、インクリメントを完全に処理する関数を使用して、インデックスにクラスまたは構造体を使用することをお勧めします。

于 2011-10-24T14:39:04.250 に答える
0

以下はすべて、Windows ではなく Unix 用です。

std::__copy_move...STLで大丈夫です。しかし、STL はそれ自体では何もしません。コードからの関数呼び出しによって、間違った引数または間違った状態で呼び出された可能性があります。あなたはそれを理解する必要があります。

seg-fault からのコア ダンプがある場合はpstack <core file name>、 を実行するだけで、クラッシュの完全なコール スタックが表示されます。次に、コードのどの部分が関与しているかを確認し、そこからデバッグ (トレース/カウント/... を追加) を開始します。

通常、このコア ファイルは読みやすい名前で取得されますが、そうでない場合は、nmまたはc++filtetc を使用して名前を分解できます。

最後にpstack、小さな cmd ライン ユーティリティです。いつでも (コアを生成した) バイナリとコア ファイルを、gdb、Sun Studio、または IDE に組み込まれたデバッガなどのデバッガにロードして、他の多くの機能とともに同じことを確認できます。情報とオプション。

HTH

于 2011-10-24T14:32:36.567 に答える
0

あなたのアルゴリズムは少し「力ずく」のようです。これは一般に、制約充足問題 (CSP) では適切な戦術ではありません。しばらく前に数独ソルバーを書きました (まだソース コードがあればよかったのですが、それは github を発見する前のことでした)。

http://en.wikipedia.org/wiki/Simulated_annealing

これは確率論的ですが、一般に、この問題 IIRC の他の方法よりも桁違いに高速でした。

チッ！

于 2011-10-24T19:12:22.750 に答える
0

関数を再帰的に何度も入力すると、セグメンテーション違反が発生する可能性があります (発生する可能性があります)。それにつながる1つのシナリオに注目しました。しかし、もっとあると確信しています。

ヒント: 関数の目的を言葉で書いてください。複雑すぎて記述できない場合は、おそらく関数を分割する必要があります...

于 2011-10-24T14:50:26.620 に答える