¿Cuándo es apropiado el retroceso recursivo?

Question

Estoy haciendo un SudokuSolver para una clase, y estoy teniendo problemas con el método de resolución. Mi solución actual utiliza retroceso recursivo (creo).

requisitos del ejercicio

int solve() - trata de resolver el rompecabezas usando la estrategia descrita anteriormente. Devuelve la cantidad de soluciones.

(La estrategia descrita anteriormente)

Cuando se asigna un número a un lugar, nunca se asignará un número que, en ese momento, entra en conflicto con la fila de la mancha, columna o cuadrado. Somos cuidadosos con la asignación de números legales a un punto, en lugar de asignar el número 1..9 y encontrar el problema más adelante en la recursión. Suponga que la grilla inicial es completamente legal, y solo haga asignaciones de puntos legales a partir de entonces.

Idea Pseudocódigo

puedo seguir esta forma iterativa para una pequeña entrada. Por ejemplo, supongamos que tengo células no resueltas Celda n. ° 1 y Celda n. ° 2. # 1 tiene posibilidades {1, 3} y # 2 tiene posibilidades {2, 3}. Entonces yo

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 

código real

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

Resultados de la Prueba

testSolveSingleSolution 
    expected 1, actual 1 

testSolveSolved 
    expected 1, actual 1 

testSolveUnsolvable 
    expected 0, actual 0 

testSolveMultiSolutions 
    expected 2, actual 7 // MAJOR PROBLEM! 

Algunas buenas explicaciones de recursiva Backtracking

• This answer a StackOverflow - solución recursiva al generador de Sudoku
• This answer a StackOverflow - dando marcha atrás en un laberinto
• This answer a StackOverflow - Vuelta atrás algoritmo para la secuencia de primer
• This answer a StackOverflow - ¿Cómo encontrar la primera solución sólo con este retroceso
• El artículo de Wikipedia sobre Backtracking
• Recursive Backtracking Explanation

pregunta

He hecho retrocesos recursivos antes, he revisado todos los enlaces anteriores y más, y sigo teniendo problemas. Creo que el problema radica en mi forma de pensar sobre cómo resolver esto. (Ver idea de seudocódigo.) ¿Es apropiado usar retroceso recursivo para una búsqueda exhaustiva? ¿Es correcto retroceder pero la implementación es incorrecta? ¿Hay algún algoritmo mejor que pueda usar que el retroceso recursivo?

Answer 1

Parece un problema de implementación. Verifica el bloque donde estás incrementando el resultado. ¿De verdad quieres incrementar para cada valor válido de esa celda? ¿Y para ese asunto, sobrescriba el valor válido anterior si hay varios que son válidos?