Pollux a écrit :
Ethaniel :
Et pourtant, ça existe !
Plus exactement, à un moment, tu te retrouves coincé avec aucune possibilité de continuer de manière sûre.
Non, lis le topic.
(ou alors tu m'as l'air d'être en bonne voie pour montrer que P != NP = EXP 
)
On ne doit pas penser à la même chose.
Allons-y donc pour un exemple concret...
Soit une grille que l'on cherche à résoudre d'une manière ou d'une autre.
Soit une case vide, ses 9 candidats sont les chiffres de 1 à 9.
Essayons de voir si le 1 convient : ah ben non, il y a déjà un 1 dans la même ligne.
Essayons de voir si le 2 convient : ah ben non, il y a déjà un 2 dans la même colonne.
Essayons de voir si le 3 convient : ah ben non, il y a déjà un 3 dans la même région.
[...]
Essayons de voir si le 7 convient : apparemment, rien ne l'interdit directement.
[...]
Finalement, seul le 7 convient, donc c'est un 7 dans cette case
détermination directe d'un chiffre par élimination des autres candidats.
Continuons la résolution, beaucoup plus loin...
Soit une case vide, et on a déjà éliminé 7 candidats, restent le 1 et le 3.
On cherche on cherche on cherche, mais
pas moyen de décider quel chiffre est le bon (et c'est de ça que je parle).
Essayons de voir si le 1 convient en l'inscrivant et en continuant la résolution : ah ben non, 14 cases remplies plus loin, on a une situation impossible, deux fois le même chiffre dans la même ligne.
Essayons de voir si le 3 convient en l'inscrivant et en continuant la résolution : apparemment, on arrive à résoudre la grille jusqu'au bout.
Finalement, seul le 3 convient, donc c'est un 3 dans cette case
détermination backtrackée d'un chiffre par élimination des autres candidats (élimination indirecte du 1, directe des autres).
La détermination backtrackée n'est pas moins logique que la détermination directe, c'est simplement moins esthétique.
D'ailleurs, beaucoup de solveurs programmés à l'arrache font du brute backtracking : on met un 1 dans la toute première case, si c'est bon on passe à la deuxième case où on met aussi un 1, mais comme ça ne marche pas on backtracke et on met un 2 à la place, etc.
L'hypothèse nécessaire autorisant le backtracking est que
la solution d'une grille est unique.
Et quand on est obligé de backtracker, ce n'est pas que la grille est mal faite, au contraire, c'est qu'elle est de niveau supérieure au sien, puisqu'aucune
technique que l'on connaît n'y vient à bout, alors que, si ça se trouve, dans notre exemple, un coup de
squirmbag (oui oui, cette technique existe vraiment
) permettait de voir immédiatement que le 1 n'était pas un candidat possible, et donc que seul reste le 3...
Et s'il y a une grille sur laquelle même toutes les techniques connues de par le monde se cassent les dents, c'est peut-être (je dis bien
peut-être) qu'il existe une toute nouvelle technique que personne n'a encore trouvée
!
)
.
une piste pour le programme ?
) permettait de voir immédiatement que le 1 n'était pas un candidat possible, et donc que seul reste le 3...
. C'est pour ça je pense que Moumou disait qu'un algorithme qui donnerait des grilles insolubles autrement que par ce moyen ne serait pas super, mais je ne vois toujours pas pourquoi ça existerait 
