11

クラス用にSudokuSolverを作成していますが、solveメソッドに問題があります。私の現在のソリューションは、再帰的なバックトラッキングを使用しています（私は思います）。

割り当て要件

intsolve（）-上記の戦略を使用してパズルを解こうとします。ソリューションの数を返します。

（上記の戦略）

スポットに番号を割り当てるときは、その時点でスポットの行、列、または正方形と競合する番号を割り当てないでください。1..9の番号を割り当てて、再帰の後半で問題を見つけるのではなく、スポットに合法的な番号を割り当てることに事前に注意を払っています。最初のグリッドはすべて合法であると想定し、その後は合法的なスポット割り当てのみを行います。

擬似コードのアイデア

小さな入力に対してこれを繰り返したどることができます。たとえば、セル＃1とセル＃2を未解決にする必要があるとします。＃1には可能性{1、3}があり、＃2には可能性{1、3}があります。私はそれから

set 1 to 1
    set 2 to 2
        hasConflicts? 0 : 1
    set 2 to 3
        hasConflicts? 0 : 1
set 1 to 3
    set 2 to 2
        hasConflicts? 0 : 1
    set 2 to 3
        hasConflicts? 0 : 1

実際のコード

public int solve() {
    long startTime = System.currentTimeMillis();
    int result = 0;

    if (!hasConflicts()) {
        Queue<VariableCell> unsolved = getUnsolved();
        reduceUnsolvedPossibilities(unsolved);  // Gets the possibilities down from all of 1-9

        if (!hasConflicts()) {
            result = solveRec(unsolved);
        }
    }

    mElapsedTime = System.currentTimeMillis() - startTime;
    return result;
}

protected int solveRec(Queue<VariableCell> unsolved) {
    if (unsolved.isEmpty()) {
        return (hasConflicts()) ? 0 : 1;
    }

    int result = 0;
    VariableCell cell = unsolved.remove();
    Iterator<String> possibilityIt = cell.getPossibilities().iterator();

    while (possibilityIt.hasNext()) {
        cell.setSymbol(possibilityIt.next());

        if (hasConflicts()) {
            possibilityIt.remove();
        } else {
            ++result;
        }
    }

    return result + solveRec(unsolved);
}

試験結果

testSolveSingleSolution
    expected 1, actual 1

testSolveSolved
    expected 1, actual 1

testSolveUnsolvable
    expected 0, actual 0

testSolveMultiSolutions
    expected 2, actual 7  // MAJOR PROBLEM!

再帰的バックトラッキングのいくつかの良い説明

質問

私は以前に再帰的なバックトラックを実行しましたが、上記のすべてのリンクを確認しましたが、まだ問題があります。問題は、これをどのように解決するかを考えることにあると思います。（擬似コードのアイデアを参照してください。）徹底的な検索に再帰的なバックトラッキングを使用することは適切ですか？バックトラックは正しいですが、実装は間違っていますか？再帰的なバックトラッキングよりも優れたアルゴリズムを使用できますか？

4

1 に答える 1

0

これは実装上の問題のようです。結果をインクリメントしているブロックを確認してください。そのセルの有効な値ごとに本当にインクリメントしますか？さらに、有効な値がいくつかある場合は、古い有効な値を上書きしますか？

于 2012-07-17T16:49:18.683 に答える