0

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で割り当てます）。その後、コピーに対して割り当てを実行します。検索への再帰呼び出しが失敗した場合は、次の桁を試すために新しいボードを作成できます。

私はもう試した：

// 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;
 }

もう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

4

2 に答える 2

2

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

再帰を使用すると、ネストされたforループを使用してフィールドにアクセスするのではなく、再帰呼び出しで次のフィールドにアクセスできます。最後のフィールドに到達するか、すべての可能性を試し、関数を終了して、アクセスした前のフィールドに戻ることができます。

補足：このタスクにダイナミックメモリを割り当てないでください：

//Board *copyBoard = new Board(*this);
Board copyBoard(*this); //if you need a copy in the first place
于 2011-12-06T15:16:45.907 に答える
1

基本的に試すことができるのは、このようなものです（疑似コードっぽい）

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(...) 関数は、ランダムな空の正方形、または残っているオプションの数が最も少ない正方形を返す可能性があります。後者を使用すると、アルゴリズムの収束がはるかに速くなります。

于 2011-12-06T16:32:40.720 に答える