Quelle différence de complexité peut-il y avoir entre trouver une solution à un puzzle Sudoku et prouver que la solution est la solution unique?

Donc, le Sudoku est généralement de , mais cette question s'étend à n 2 × n 2 puzzles avec n > 3 également. Il existe de nombreuses règles polynomiales de déduction de temps qui peuvent progresser dans la recherche d'une solution à un puzzle Sudoku. Mais parfois, il peut être nécessaire de deviner des valeurs et de suivre des chaînes de conclusions pour éliminer la valeur d'une cellule ou une combinaison de valeurs de cellules. Cependant, une fois qu'une solution valide est trouvée, cela ne garantit pas que la solution est UNIQUE. Un puzzle Sudoku valide ne devrait avoir qu'une seule solution valide, mais lors de la génération de puzzles aléatoires, cela peut prendre un calcul supplémentaire pour vérifier.$9 \times 9$$n^2 \times n^2$$n > 3$

Donc, ma question est, si nous autorisons un certain ensemble de règles de déduction de temps polynomiales (disons, l'ensemble le plus commun décrit dans la stratégie de Sudoku), ainsi que des valeurs de devinettes et en suivant les conclusions, alors combien plus difficile peut-il être de déterminer qu'il y a une solution unique à un puzzle donné, par rapport à la recherche d'une seule solution, en termes de nombre de solutions non uniques? Existe-t-il une différence asymptotique pour certaines classes de puzzles?

$m$$m$

Si je vous comprends bien, vous essayez de vérifier les puzzles Sudoku que votre logiciel a générés pour voir s'ils sont valides.

Si seul le fait d'être «valide» est intéressant, Yuval Filmus vous a déjà indiqué une preuve qu'il est NP complet.

Cependant, si le but est de trouver de nouveaux puzzles Sudoku qu'une personne aimera résoudre, le problème n'est pas aussi difficile. (Devoir deviner beaucoup de valeurs, car le puzzle n'est pas résolu en utilisant la «logique» n'est pas amusant!) Par conséquent, personnellement, je limiterais le nombre de suppositions à 4 au maximum et rejetterais tout puzzle qui ne peut pas être prouvé solution unique dans la limite de ce que vous considérez comme raisonnable.

Faire ce qui précède, utiliser le suivi arrière standard pour visiter toutes les suppositions possibles (dans votre limite) et montrer qu'il n'y a qu'une seule solution est beaucoup plus facile que NP complet.

De plus, vous pouvez évaluer la difficulté d'un puzzle en fonction de la complexité des règles de déduction dont il a besoin et du nombre de suppositions nécessaires.

Afin de prouver qu'un puzzle est unique, toute cellule dans laquelle une supposition devait être faite doit être ramifiée. Lorsque vous effectuez une recherche pour trouver simplement une réponse, cela se fait généralement avec un retour en arrière, où la solution est le premier chemin dans l'arbre de décision qui mène à un tableau complet. Afin de prouver l'unicité, vous devez montrer qu'un seul chemin mène à une solution valide. C'est là que les choses deviennent très difficiles à définir en termes de durée d'exécution. La complexité est extrêmement liée au problème actuel. Si vous regardez le pire des cas, ce qui est extrêmement peu probable, alors ils peuvent être considérés comme la même complexité.

Dans le pire des cas, lors de la résolution, la solution se trouve dans la dernière branche possible de l'arborescence qui peut être recherchée. L'arbre entier a dû être recherché pour le trouver, tandis qu'une recherche d'unicité nécessiterait également la même recherche, en parcourant exactement les mêmes chemins.

En réalité, cependant, ce n'est pas le cas, et avec presque tous les cas impliquant la recherche de conceptions combinatoires, la recherche d'une solution est toujours plus rapide que la recherche de toutes les solutions.

En général, ces deux problèmes sont fermement ancrés dans des temps d'exécution exponentiels, sinon pire.