C++ - sudokuのゲームを解決する

Question

私はC++を初めて使い、家の割り当て（sudoku）をしなければならない。私は問題に固執しています。

問題は、スードクを解く検索関数を実装することです。

命令： 解決策を見つけるために、再帰的検索は以下のように使用されます。 桁（d1 .... dn）（n> 1）のフィールドがまだ割り当てられていないとします。次に、最初に にフィールドを割り当てて、伝播を実行してから、 を再帰的に実行しようとします。 伝播が失敗することがあります（フィールドは になります）。その場合、検索は失敗し、 フィールドのいずれかの異なる桁を試してみる必要があります。検索が再帰的であるため、最後に考えられるフィールドの次の数字が になります。いずれの桁も解に至らない場合、検索は再び失敗します。 のこれは、前のフィールドと異なる桁の試行につながります。

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

私が試した：

// Search for a solution, returns NULL if no solution found 
Board* Board::search(void) { 
    // create a copy of the cur. board 
    Board *copyBoard = new Board(*this); 
    Board b = *copyBoard; 

    for(int i = 0; i < 9; i++){ 
     for(int j = 0; j < 9; j++){ 

       // if the field has not been assigned, assign it with a digit 
      if(!b.fs[i][j].assigned()){ 
       digit d = 1; 

        // try another digit if failed to assign (1 to 9) 
       while (d <=9 && b.assign(i, j, d) == false){ 
         d++; 


         // if no digit matches, here is the problem, how to 
         // get back to the previous field and try another digit? 
         // and return null if there's no pervious field 
       if(d == 10){ 
         ... 
        return NULL; 
       } 
      } 
     } 
    } 
    return copyBoard; 
} 

もう一つの問題は、再帰呼び出しを使用することがどこにあるのでしょうか？任意のヒント？どうも！

完全な命令は、ここで発見されてすることができます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

Answer 1

あなたのコードには再帰がありません。一度各フィールドにアクセスして値を割り当てることはできません。問題は、フィールド（3,4）に5を割り当てることができる可能性があり、フィールド（6,4）に到達して5 、4）。最終的に、（3,4）に戻って別の値を試すまで、再帰をやめる必要があります。

再帰を使用すると、フィールドを参照するためにネストされたforループを使用することはできませんが、再帰呼び出しで次のフィールドにアクセスすることがあります。最後のフィールドに到達するか、すべての可能性を試してから、直前のフィールドに戻る機能を残してください。

---

追記：間違いなく、このタスクのために動的メモリを割り当てません。

//Board *copyBoard = new Board(*this); 
Board copyBoard(*this); //if you need a copy in the first place 

Answer 2

基本的に何を試すことができますが、このような何か（pseudocode'ish）

bool searchSolution(Board board) 
{ 
Square sq = getEmptySquare(board) 
if(sq == null) 
    return true; // no more empty squares means we solved the puzzle 

// otherwise brute force by trying all valid numbers 
foreach (valid nr for sq) 
{ 
    board.doMove(nr) 

    // recurse 
    if(searchSolution(board)) 
     return true 

    board.undoMove(nr) // backtrack if no solution found 
} 

// if we reach this point, no valid solution was found and the puzzle is unsolvable 
return false; 

} 

getEmptySquareです（...）関数は、空の空の四角形または最小のオプション数を持つ正方形を返します。 後者を使用すると、アルゴリズムがはるかに高速に収束します。