¿Cuánta diferencia de complejidad puede haber entre encontrar una solución para un rompecabezas de Sudoku y PROPORCIONAR que la solución es la solución única?

Por lo general, Sudoku es , pero esta pregunta se extiende a n 2 × n 2 rompecabezas con n > 3 también. Hay muchas reglas de deducción de tiempo polinomial que pueden avanzar en la búsqueda de una solución para un rompecabezas de Sudoku. Pero a veces, puede ser necesario adivinar valores y seguir cadenas de conclusiones para eliminar el valor de una celda o una combinación de los valores de las celdas. Sin embargo, una vez que se encuentra una solución válida, esto no garantiza que la solución sea ÚNICA. Un rompecabezas de Sudoku válido debe tener solo una solución válida, pero al generar rompecabezas aleatorios, esto puede requerir un cálculo adicional para verificar.$9 \times 9$$n^2 \times n^2$$n > 3$

Entonces, mi pregunta es, si permitimos un cierto conjunto de reglas de deducción de tiempo polinomial (digamos, el conjunto más común descrito en la estrategia de Sudoku), junto con adivinar valores y seguir las conclusiones, entonces, ¿cuánto más difícil puede ser determinar que hay ¿Una solución única para un rompecabezas dado, frente a la búsqueda de una sola solución, en términos de la cantidad de soluciones no únicas? ¿Existe una diferencia asintótica para ciertas clases de rompecabezas?

Yato y Seta muestran que por cada constante , dadas m soluciones a un rompecabezas de Sudoku, es NP completo para determinar si hay otra solución. Muestran que otros rompecabezas también satisfacen la misma propiedad.$m$$m$

Si te entiendo correctamente, estás intentando verificar los rompecabezas de Sudoku que tu software ha generado para ver si son válidos.

Si solo ser "válido" es de interés, Yuval Filmus ya le ha indicado una prueba de que está NP completo.

Sin embargo, si el objetivo es encontrar nuevos rompecabezas de Sudoku que una persona disfrutará resolviendo, el problema no es tan difícil. (¡Tener que adivinar muchos valores, debido a que el rompecabezas no se puede resolver usando "lógica" no es divertido!) Por lo tanto, personalmente limitaría el número de conjeturas a un máximo de 4 y rechazaría cualquier rompecabezas que no se pueda demostrar que tenga La solución única dentro de la limitación de lo que usted considera es razonable.

Haciendo lo anterior, utilizando el seguimiento estándar para visitar todas las conjeturas posibles (dentro de su límite), y mostrar que solo hay una solución es mucho más fácil que completar NP.

Además, puede evaluar la dificultad de un rompecabezas en función de la complejidad de las reglas de deducción que necesita y la cantidad de conjeturas que se necesitaban.

Para demostrar que un rompecabezas es único, cualquier celda en la que haya que adivinar debe ser ramificada. Al hacer una búsqueda para simplemente encontrar una respuesta, esto generalmente se hace con retroceso, donde la solución es el primer camino en el árbol de decisión que conduce a un tablero completo. Para demostrar la unicidad, debe mostrar que solo un camino conduce a una solución válida. Aquí es donde las cosas se vuelven muy difíciles de definir en términos de tiempo de ejecución. La complejidad está extremadamente ligada al problema real en cuestión. Si está mirando el peor de los casos, que es extremadamente improbable que ocurra, entonces se puede considerar la misma complejidad.

En el peor de los casos, al resolver, la solución está dentro de la rama final posible del árbol que se puede buscar. Se tuvo que buscar todo el árbol para encontrarlo, mientras que una búsqueda de unicidad también requeriría la misma búsqueda, recorriendo exactamente los mismos caminos.

Sin embargo, de manera realista, este no es el caso, y con casi todos los casos relacionados con la búsqueda de diseños combinatorios, la búsqueda de una solución siempre es más rápida que la búsqueda de todas las soluciones.

En general, ambos problemas están firmemente arraigados en tiempos de ejecución exponenciales, si no peor.