-1

私は数独ソルバーを作成しましたが、数独が解ける場合は問題なく動作します。ただし、数独が解決できない場合は、バックトラック時にパズルの元の番号が変更されます。

bool Sudoku::solve(int row, int col){
if (board[row][col] != 0){
    int next_col = col;
    int next_row = row;

    next_col++;

    if (next_col > 8){
        next_row++;
        next_col = 0;
    }

    if (next_row > 8){
        return true;
    } else {
        if (solve(next_row, next_col))
            return true;
    }
}

for (int number = 1; number <= 9; number++){
    board[row][col] = number;

    if (check_row(row, number)
     && check_col(col, number)
     && check_box(row, col, number)){
        int next_row = row;
        int next_col = col+1;

        if (next_col > 8){
            next_col = 0;
            next_row++;
        }

        if (next_row > 8){
            return true;
        }

        if (solve(next_row, next_col))
            return true;
     }
}

board[row][col] = 0;
return false;

}

ボードは2Dint配列です。整数の代わりにある種の構造を使用できることは知っています。整数が元々そこにあったかどうかを格納しますが、このソリューションは私にはあまり魅力的ではありません。他に方法はありますか？

4

2 に答える 2

2

冒頭のチェックで、セルをセットすると、

if (board[row][col] != 0){
    int next_col = col;
    int next_row = row;

    next_col++;

    if (next_col > 8){
        next_row++;
        next_col = 0;
    }

    if (next_row > 8){
        return true;
    } else {
        if (solve(next_row, next_col))
            return true;
    }
}

を追加

else {
    return false;
}

または最後をに変更します

return solve(next_row, next_col);

指定された数値を変更しないようにします。そのままで、パズルを解くことができない場合 (元のセルを解くことができた前のセルを間違って推測した後でも)、喜んでセル内の数字を変更します。

于 2013-03-21T00:06:21.830 に答える
0

訪問したすべての場所のセットを作成できます。

実装例std::set<pair<int, int> > visitedは、訪問した各場所を含む を作成することです。その場所が訪問された場合は、値を変更しないでください。

于 2013-03-21T00:03:29.283 に答える