Kiedy rekursywne kopiowanie jest odpowiednie?

Question

Robię SudokuSolver dla klasy i mam problem z metodą rozwiązania. Moje obecne rozwiązanie wykorzystuje rekursywny backtracking (chyba).

przypisania Wymagania

int solve() - stara się rozwiązać zagadkę przy pomocy strategii opisanej powyżej. Zwraca liczbę rozwiązań.

(Strategia opisana powyżej)

Podczas przypisywania numeru do miejsca, nigdy przypisać numer, że w tej chwili, konflikty z rzędu rzutu za, kolumny lub kwadratu. Dokładamy starań, aby przypisać numery prawne do miejsca, a nie przypisywać numer 1..9 i znaleźć problem później w rekursji. Załóżmy, że początkowa siatka jest legalna i od tego czasu wykonujesz tylko legalne zlecenia dodatkowe.

Pseudokod Idea

mogę śledzić to iteracyjnie dla małego wejścia. Na przykład powiedzmy, że mam nierozwiązane komórki Nr komórki 1 i Nr komórki 2. # 1 ma możliwości {1, 3}, a # 2 ma możliwości {2, 3}. Chciałbym następnie

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 

rzeczywisty kod

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

Wyniki testu

testSolveSingleSolution 
    expected 1, actual 1 

testSolveSolved 
    expected 1, actual 1 

testSolveUnsolvable 
    expected 0, actual 0 

testSolveMultiSolutions 
    expected 2, actual 7 // MAJOR PROBLEM! 

jakiś dobry Objaśnienia rekurencyjnych Backtracking

• This answer do StackOverflow - rekurencyjne rozwiązanie sudoku generator
• This answer do StackOverflow - Backtracking w labiryncie
• This answer do StackOverflow - Backtracking algorytm prime sekwencji
• This answer do StackOverflow - Jak znaleźć pierwsze rozwiązanie tylko z tego backtracking
• artykuł na Backtracking
• Recursive Backtracking Explanation

Pytanie

Przedtem robiłem rekursję wstecz, sprawdziłem wszystkie powyższe linki powyżej i więcej, i nadal mam problemy. Myślę, że problem leży w moim rozmyślaniu o tym, jak rozwiązać ten problem. (Patrz Pseudocode Idea.) Czy należy stosować rekursywne wycofywanie w celu wyczerpującego wyszukiwania? Czy poprawne jest cofnięcie, ale implementacja jest nieprawidłowa? Czy istnieje lepszy algorytm, którego mogę użyć, niż rekursywne wycofywanie?

Answer 1

To wygląda na problem z implementacją. Sprawdź blok, w którym zwiększasz wynik. Czy na pewno chcesz inkrementować każdą prawidłową wartość tej komórki? I w tym przypadku zastąpić starszą prawidłową wartość, jeśli jest kilka ważnych?