Automatiser la réponse au Sudoku

Version imprimable

Voir 40 message(s) de cette discussion en une page

23/02/2006, 09h36
Sivrît

Citation:

Envoyé par Tellmarch

et trouverait ainsi la bonne valeur immédiatement.

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

Citation:

Envoyé par Tellmarch

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.

Citation:

Envoyé par Tellmarch

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... :?:
23/02/2006, 10h06
Tellmarch

Citation:

Envoyé par Sivrît

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...

Citation:

Envoyé par Sivrît

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...

Citation:

Envoyé par Sivrît

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....

Citation:

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]
23/02/2006, 10h30
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.
23/02/2006, 10h40
Tellmarch

Citation:

Envoyé par Miles

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 :)
23/02/2006, 11h10
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.
23/02/2006, 13h29
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.
23/02/2006, 19h14
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 :)
24/02/2006, 08h42
2Eurocents

Citation:

Envoyé par 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 :)

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

Citation:

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 ...
24/02/2006, 09h22
Sivrît

Citation:

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 8O Ca doit heurter mon côté cartésien :(
24/02/2006, 10h02
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) !
24/02/2006, 10h42
Tellmarch

Citation:

Envoyé par 2Eurocents

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

Citation:

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 :roll:
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.

Citation:

Envoyé par Miles

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é :roll:
24/02/2006, 10h45
Matthieu Brucher

Et maintenant, fais la somme des C(n,k), et révise toi tes cours de complexité.
24/02/2006, 10h52
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 ;)
24/02/2006, 10h59
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).
24/02/2006, 11h02
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 :)
24/02/2006, 13h16
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.
24/02/2006, 13h21
Sivrît

Citation:

Envoyé par Tellmarch

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

Moi je veux bien ! :)
J'ai beau essayer j'arrive pas à voir les deux procédés comme équivalents. Que leurs complexités le soit me semble même normal, mais avoir la même complexité ne rend pas deux algorythmes identiques.

Citation:

Envoyé par Tellmarch

en bref tu as une seule regle, qui dit "ça doit etre la meme chose que ce que trouverait une recherche exhaustive"

Ben ça vaudrait mieux. Si le résultat n'est pas le même ça va être sacrément mauvais signe pour notre raisonnement ! :oops:

En tout cas une règle peut tout à fait faire abstraction de la taille du problème. Par exemple :
"Si N valeurs ne peuvent être prises que par N cases d'un groupe, alors ces cases ne peuvent prendre aucune autre valeur"
Manifestement ce n'est pas une règle facile à implémenter (de ce point de vue je préfère largement implémenter un algo récursif) ni facile à appliquer. Par contre je la trouve conceptuellement plus élégante que de tester brutalement toutes les combinaisons jusqu'à trouver la bonne. L'idée est d'améliorer sa compréhension du jeu, pas de tout déléguer à une machine et de compter sur ses méga hertz.

Même si ça ne va pas plus vite il y a une application. C'est peut-être juste moi :oops: mais je suis incapable d'enchainer toutes les possibilités par essai/erreur. Pour un humain c'est juste impraticable. Par contre repérer des schémas et des groupements pour y appliquer des règles m'est naturel.

Tellmarch> Je viens juste de me dire que dans l'idée, les règles permettent de limiter l'ensemble possibilités par déduction... alors qu'une recherche les élimine une par une à chaque contradiction trouvée. C'est l'équivalence dont tu parles ?

en gros, le groupement sur une case correspondra exactement à une recherche de profondeur 1, sur 2 cases à une recherche de profondeur 2, etc...

bon je vais essayer de formaliser un algo pour que ça soit plus clair :

Soit C l'ensemble des contraintes du probleme.
Dans notre cas, C = D + E + F + G, ou :
D = {Dij : les nombres restants sur la case i,j}
E = {Gij : les places possibles pour le nombre j dans la ligne i}
F = {Gij : les places possibles pour le nombre j dans la colonne i}
G = {Gij : les places possibles pour le nombre j dans le carré i}

L'algorithme générique de parcours est alors le suivant (j'ai pas mal simplifié pour insister sur les elements essentiels de l'algo)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 Fonction résoudre : Pour i allant de 1 à l'infini Parcours( à la profondeur i) Fonction Parcours (int p : profondeur) Si il y a une contradiction Alors retour soit c la contrainte de cardinal minimal, Pour tous les choix possibles dûs à c, faire jouer le coup, mettre à jour la liste des contraintes; Parcours (à la profondeur p-1) Fin Pour
Prenons alors les regles de Miles, et regardons ce que ça donne.
L'existence d'un sous groupe restreignant le choix de k valeurs correspond exactement à l'appel à notre procedure de recherche, à la profondeur k, avec la meme complexité.

Au début Miles parlait de 3 regles, elles sont toutes contenues dans ce processus essai/erreur, avec la meme complexité.
Maintenant il semble qu'il soit revenu à l'idée d'une seule regle, mais cette regle est exactement :
"quelque soit k, l'algo de recherche à la profondeur k fixerait ces valeurs"
Donc sa regle c'est simplement d'appliquer le parcours...

Un tel algorithme générique de backtrack appliqué au sudoku se code en moins d'une vingtaine de lignes, et personnellement je trouve ça plus élégant que :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 bool SolverCore::solve() { do { do { do { do { do { do { popImpossibleValues(); }while(applyRule0()); }while(applyRule1()); }while(applyRule2()); }while(applyRule3()); }while(applyRule4()); }while(applyRule5());
sachant que toutes les regles sont contenues dans le backtrack, je trouve ça assez inutile :roll:

24/02/2006, 15h15
Matthieu Brucher

Citation:

Envoyé par 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 :)

Faux, c'est une des règles les plus élémentaires et elle ne résoud pas tout, TRES loin de là. Tu devrais te renseigner un peu.

graphito > une grille de Sudoku a une seule solution, c'est une règle de base.
24/02/2006, 15h21
Tellmarch

Bon comme tu n'arretes pas de changer d'avis, j'aimerais bien que tu me dises de quoi tu parles exactement...
- Tu as combien de regles?
- Lesquelles précisement?

Voir 40 message(s) de cette discussion en une page