Discussion :

[goomy]

Bonjour

Je ne suis pas informaticien, mais juste joueur de sudoku.

Pour tenter de résumer ma méthode en la rendant "logique" :
-> remplir les cases vides avec les différentes possiblités en prenant appui sur la colonne, la ligne et le carré 3x3 de la case en question.
-> remplir les cases qui ne comportent qu'une seule valeur
-> trouver les paires (comparer 2 à 2 les cases) d'une ligne, d'une colonne et d'un carré 3x3 et gommer en conséquence les valeurs de la paire sur la ligne correspondante, sur la colonne ou dans le carré.
-> regarder à nouveau s'il y a des valeurs seules. Si oui les inscrire et refaire l'analyse des paires, sinon on passe au triplet.
-> trouver les triplets d'une ligne, colonne ou carré et gommer en conséquence.
-> regarder à nouveau s'il y a des valeurs seules, puis de nouvelles paires, puis de nouveaux triplets.
-> trouver les quadruplets d'une ligne, colonne ou carré et gommer en conséquence.
-> regarder à nouveau s'il y a des valeurs seules, puis de nouvelles paires, puis de nouveaux triplets, puis de nouveaux quadruplets.
-> trouver les quintuplets d'une ligne, colonne ou carré et gomme en conséquence.
-> regarder à nouveau s'il y a des valeurs seules.
-> Quand j'ai fini de faire ces différentes analyses, soit le jeu est rempli, soit il reste des solutions et il faut faire une étape de testing, à partir d'une paire faire un choix et soit on complète le grille soit il y a une contradiction et c'est l'autre valeur qu'il faut mettre ((en général les grilles les plus difficiles que j'ai faites comportait une étape de testing avec peu de chiffres inscrit mais une seule étape était nécessaire).

Pour des grilles difficiles, je vous conseille ce petit recueil qui propose vraiment des grilles difficiles (les ceintures noires demandent vraiment du temps et de la réflexion). Si vos programmes résolvent ces grilles alors c'est qu'ils sont sans doute performants.

[Tellmarch]

Pour en résoudre beaucoup, même les plus difficiles, c'est TOUJOURS par un raisonnement logique et sans suppositions qu'on peut trouver les nombres à trouver (j'inclus dans ce raisonnement logique ce que vient d'écrire Tellmarch, ce n'est pas un raisonnement essai/erreupour moi)

Alors on n'a pas la meme définition d'un raisonnement essai/erreur
pour moi, tous les raisonnements que l'on peut appliquer dans le sudoku sont basés sur l'essai/erreur.

Par exemple si l'on a une colonne remplie à 8 cases, pour la derniere case, on peut trouver la bonne valeur. Pourquoi? parceque toutes les autres valeurs donneraient une erreur immédiate.

Un programme informatique basé sur l'essai/erreur, ce qui correspond à un parcour de l'arbre des possibilité, ferait exactement la meme chose :
pour les 8 branches correspondant aux 8 numéros deja pris, il aboutirait à une contradiction directe, remonterait dans l'arbre, et trouverait ainsi la bonne valeur immédiatement.


Apres, il est bien sur possible de rajouter des "regles" artificielles pour oublier ce qui est à la base du raisonnement, l'essai/erreur.
par exemple la regle "si l'on a 8 cases remplies dans une colonne, alors la 9eme est la valeur qui n'était pas dans la colonne".
Mais toutes ces regles ne sont que des conséquences directe de l'essai/erreur, et un simple programme qui se contente de faire un parcours les retrouverait trivialement.

De plus un programme doit nécessairement implémenter l'algorithme général de recherche, car quelque soit l'ensemble de regles que l'on donne, on pourra toujours trouver une grille de sudoku particuliere dans laquelle aucune de ces regles ne s'appliquera, et où il faudrait inventer une nouvelle regle spécifique, qui découlerait encore une fois du principe d'essai/erreur, qui permettrait de résoudre la grille.

C'est pour ça que je pense qu'il n'est pas nécessaire d'implementer une bibliotheque de regles spécifiques à appliquer dans un solveur de sudoku, alors qu'elles découleront toutes naturellement de l'algorithme général d'essai/erreurs.

[Sivrît]

et trouverait ainsi la bonne valeur immédiatement.

Trouver après 8 essais infructeux peut-il encore être qualifié d'immédiat ?

par exemple la regle "si l'on a 8 cases remplies dans une colonne, alors la 9eme est la valeur qui n'était pas dans la colonne".
Mais toutes ces regles ne sont que des conséquences directe de l'essai/erreur, et un simple programme qui se contente de faire un parcours les retrouverait trivialement.

Là je ne suis pas d'accord : la règle "si l'on a 8 cases remplies dans une colonne, alors la 9eme est la valeur qui n'était pas dans la colonne" n'est pas une conséquence de tentatives infructueuses mais une implication des règles du jeu. C'est une conséquence logique des règles du jeu que l'on peut prouver et qui est aussi valide que les règles initiales (et non pas "artificielles").

On peut en faire la preuve par l'absurde, mais ce n'est pas pour autant un processus d'essai/erreur.

Un programme qui teste naïvement toutes les possibilités ne retrouvera pas cette règle mais seulement le résultat. Il ne sera pas capaple d'en faire l'abstraction, et si d'autres cases sont libres il peut attaquer la grille par ces dernières, alors qu'une meilleur compréhension des règles lui aurait permit de couper sont arbre très efficacement.

car quelque soit l'ensemble de regles que l'on donne, on pourra toujours trouver une grille de sudoku particuliere dans laquelle aucune de ces regles ne s'appliquera

Peut-être, mais ça reste à démontrer (si tu as ça fera des heureux !). C'est d'ailleurs là dessus que tourne beaucoup la discussion. Peut-on trouver un ensemble de règles fini tel qu'une grille incomplète à laquelle aucune règle ne s'applique ait obligatoirement plusieurs solutions ?


Par contre il existe des programmes capables de réaliser des preuves formelles... Je me demande si l'un d'eux pourrait tirer ses propres déductions des règles du jeu... :

[Tellmarch]

Trouver après 8 essais infructeux peut-il encore être qualifié d'immédiat ?

oui... les ordinateurs font plusieurs milliards d'opérations par secondes...

Il ne sera pas capaple d'en faire l'abstraction, et si d'autres cases sont libres il peut attaquer la grille par ces dernières, alors qu'une meilleur compréhension des règles lui aurait permit de couper sont arbre très efficacement.

là je ne suis pas d'accord...
ça n'a aucune importance si le programme commence par les autres cases, il arrivera tres vite à la bonne case.
Et l'algorithme sera de toute façon au moins aussi rapide en complexité qu'un algo de recherche de motifs pour appliquer les "regles" que l'on rajouterait. Par exemple le programme commencerait aussi à chercher à appliquer des motifs là ou il n'y en a pas...

Peut-être, mais ça reste à démontrer (si tu as ça fera des heureux !). C'est d'ailleurs là dessus que tourne beaucoup la discussion. Peut-on trouver un ensemble de règles fini tel qu'une grille incomplète à laquelle aucune règle ne s'applique ait obligatoirement plusieurs solutions ?

Bien sur qu'on peut en trouver un, le sudoku est borné, mais il y aura des millions de regles....

Par contre il existe des programmes capables de réaliser des preuves formelles... Je me demande si l'un d'eux pourrait tirer ses propres déductions des règles du jeu... :

Si c'est bien ce dont tu parles, je travaille sur ce genre de programmes, mais ils ne permettent en général pas d'inventer de nouvelles déduction, leur role est de vérifier la preuve donnée par l'humain (et éventuellement trouver des fragments de preuves plus ou moins triviaux...)[/quote]

[Matthieu Brucher]

Tellmarch, tu veux faire un solveur par backtracking, OK, d'autres préfèrent trouver des règles qu'un humain pourrait utiliser. Tout raisonnement sur ce jeu a un raisonnement par l'absurde derrière, seulement, je préfère l'élégance à la force brute, d'autres aussi. Toi peut-être pas, alors arrête, merci.

[Tellmarch]

Tellmarch, tu veux faire un solveur par backtracking, OK, d'autres préfèrent trouver des règles qu'un humain pourrait utiliser. Tout raisonnement sur ce jeu a un raisonnement par l'absurde derrière, seulement, je préfère l'élégance à la force brute, d'autres aussi. Toi peut-être pas, alors arrête, merci.

je trouve pas ça élégant de coder des algos spécifiques recouverts par le cas général en plus du cas général, sans gain d'efficacité.
Enfin c'est mon point de vue, comme tu dis ça a l'air assez inutile d'en discuter plus

[Tellmarch]

pour ce qui est de la preuve que les regles d'inférences ne suffisent pas, il faut bien sur se placer dans le cas général de taille n comme je l'ai dit précedement.

Alors Sudoku est NP-complet (il se réduit à partir du probleme des carrés latins).

Or l'application des regles d'inférence donnerait une solution en temps polynomial.

Donc il existe des grilles non résolubles par l'utilisation des regles d'inférence, ou alors P=NP.

[Matthieu Brucher]

Oui, le problème est NP-complet, mais non le temps de résolution par règle n'est pas polynomial pour un sou.

[Tellmarch]

c'est curieux, je ne suis pas le seul à dire ça...
cf par exemple http://sat.inesc-id.pt/~ines/publications/aimath06.pdf, début de la page 3.

cet article a été présenté à la 9th International Symposium on Artificial Intelligence and Mathematics, January 2006., il est donc censé etre fiable...


Tu noteras aussi du coup la restriction effectuée dans l'articles aux problemes résolus sans recherche.


ou alors ce que tu appelles résolution par regle est encore autre chose, encore plus inutile que ce que je pensais

[2Eurocents]

c'est curieux, je ne suis pas le seul à dire ça...
cf par exemple http://sat.inesc-id.pt/~ines/publications/aimath06.pdf, début de la page 3.

cet article a été présenté à la 9th International Symposium on Artificial Intelligence and Mathematics, January 2006., il est donc censé etre fiable...


Tu noteras aussi du coup la restriction effectuée dans l'articles aux problemes résolus sans recherche.


ou alors ce que tu appelles résolution par regle est encore autre chose, encore plus inutile que ce que je pensais

Article intéressant, au demeurant, dont je cite ici la partie qui m'intéresse le plus, dans le préambule :

Each puzzle has a unique solution and does not require the use of trial and error or guessing, i.e., each puzzle is solved merely with 'reasoning'.

Cette phrase me suffit à légitimer toutes les recherches de résolutions par règles et à exclure tant le "back-tracking" que les combinaisons massives.

La résolution peut donc être menée de manière purement itérative sur un ensemble de règle et ne nécessite pas la construction d'arbres de recherches ou la collecte de points de retour en arrière.

Après, la transformation du problème dans un autre formalisme permettant d'appliquer d'autres méthodes est un domaine différent ...

[Sivrît]

In the remainder of this paper, we will only consider Sudoku puzzles
that have these properties, i.e.:
Property 1 - Sudoku puzzles that have only one solution.
Property 2 - Sudoku puzzles that can be solved with only reasoning, i.e., with no search.

D'un autre côté ceci (page 2) sous entend que ce n'est pas toujours le cas. L'introduction fait peut-être référence aux grilles "officielles" qui sont publiées.

... et malgrès tout, l'idée que la recherche exaustive puisse être obligatoire me choque presque Ca doit heurter mon côté cartésien

[Matthieu Brucher]

Sans recherche, sans déduction, c'est effectivement 90% des grilles, celles solvables simplement par les règles appelées naked and hidden single. C'est sûr que là, c'est polynomial. Mais on rajoute la recherche des sous-groupes, les doublets, triplets, ... c'est déjà un C(n,k) !

[Tellmarch]

Article intéressant, au demeurant, dont je cite ici la partie qui m'intéresse le plus, dans le préambule :

Each puzzle has a unique solution and does not require the use of trial and error or guessing, i.e., each puzzle is solved merely with 'reasoning'.

Cette phrase me suffit à légitimer toutes les recherches de résolutions par règles et à exclure tant le "back-tracking" que les combinaisons massives.

Il faut apprendre à mieux lire les articles et à les comprendre
justement cet article se limite à ces problemes, qui ne sont pas la totalité des problemes.
La démonstration en est meme donnée dans l'article, page 3 comme je l'ai dit plus haut.

Sans recherche, sans déduction, c'est effectivement 90% des grilles, celles solvables simplement par les règles appelées naked and hidden single. C'est sûr que là, c'est polynomial. Mais on rajoute la recherche des sous-groupes, les doublets, triplets, ... c'est déjà un C(n,k) !

oui, en gros un C(n,2) pour les paires, C(n,3) pour triplets, etc...
Et c'est justement polynomial, toi tu devrais réviser tes cours de complexité

[Matthieu Brucher]

Et maintenant, fais la somme des C(n,k), et révise toi tes cours de complexité.

[Tellmarch]

tu es en train de dire que tu fais la somme sur n regles... je croyais que tu voulais un nombre constant de regles
Forcement si tu donnes toutes les regles correspondant à la taille sur laquelle tu travailles, c'est strictement équivalent à une recherche exhaustive, et donc la complexité est la meme.
Reflechis avant de poster

[Matthieu Brucher]

Le problème avec les gens comme toi, c'est qu'ils ne veulent pa comprendre.
Il y a une seule règle, mais cette règle est en temps exponentiel. Une seule règle qui cherche les sous-groupes, des sous-groupes de taille différente car à chaque taille de grille, il y a plus ou moins de sous-groupe possibles, chacun ayant un temps de résolution en C(n,k).

[Tellmarch]

ce que toi tu comprends pas, c'est que ce que fait cette regle c'est exactement équivalent à une recherche en profondeur, ça a la meme complexité, ça trouve les memes choses...
Chercher tous les sous groupes de taille de plus en plus grande, c'est juste une dérecursification du parcours...
en bref tu as une seule regle, qui dit "ça doit etre la meme chose que ce que trouverait une recherche exhaustive"

je vais finir par te faire un dessin pour que tu comprennes

[Graffito]

Bonjour,

Dire qu'une grille de SUDOKU a une seule solution est simplement absurde. Le nombre de solutions dépend du nombre de chifres connus au départ. Par exemple, si on connait 1 chiffre unique, disons au centre, on voit bien qu'on a au moins 4 solutions symétriques, plus certainement quelques milliers d'autres...

La première phase de l'algo de résolution est assez simple à mettre en oeuvre :
sachant que chaque case vide à un nombre fini de possibilités (9 hors contexte), on envisage chaque case une à une et on réduit ce nombre grace au cases dèjà remplies. Dés qu'il ny a plus qu'une possibilité dans une case, on recommence le processus.

La deuxième phase est un peu plus compliquée :
consiste à traiter les lignes ou colonnes de chaque carré avec 2 ou 3 cases inconnues et à déterminer la liste des chiffres que l'on ne trouve pas dans les possibilités des autres cases du carré. Si cette liste contient un nombre de chiffres identique à celui des cases manquante de la ligne ou colonne : on obtient une contrainte ( exemple : on sait que la colonne contiendra un 8, un 2 et un 5 à placer dans les 3 cases, mais on ignore l'ordre). Toutefois cette info permet de réduire les possibilités pour la meme ligne ou colonne des autres carrés.

Si on résoud qqchose grace à cette méthode, on recommence en début de phase 1.

Troisième phase :
On a dèjà bien élagué et même pour une grille diabolique, il ne reste plus beaucoup d'incertitudes. Là, je ne vois plus d'autre méthode que d'envisager un arbre de possibilités.

[random]

Bonjour,

Dire qu'une grille de SUDOKU a une seule solution est simplement absurde. Le nombre de solutions dépend du nombre de chifres connus au départ

Avec un bémol les règles prévoient que les chiffres connus au départ n'autorisent qu'une solution

D'ailleurs quand la solution est publiée elle ne comporte qu'une réponse.

Un problème de Sudoku qui autorise plusieurs réponses n'est pas un problème de Sudoku

une grille vierge autorise un grand nombre de problèmes mais ce n'est pas un
problème de Sudoku

ce que tu nous proposes c'est un problème d'échec avec l'échiquier mais sans les pièces.

[méphistopheles]

remarque, c'est comme ça que l'on arrive à faire des bots d'échecs. De même, pour résoudre des sudokus diaboliques et à plus forte raisons pour en créer, il faut être capable d'envisager les solutions possibles (pour n'en trouver qu'une soit.) ça me rapelle un sudoku de mauvaise qualité (20 min) que je n'arivais pas à résoudre, j'avais quatres cases vides et elles semblais toutes possibles... j'ai pu vérifier qu'il y avais 8 solutions possibles à ce sudoku (je sait, ce n'en est pas un). J'ai également essayer de générer de cette manière tous les sudokus possible: comme la barre de progression n'avait pas bougé au bout de 24h (et 450 000 solutions trouvées) j'ai décidé d'aretter là.

il y a un autre type de grille que je te défie de résoudre sans cela: je te l'enverrai si tu veux.