Discussion :

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

[Sivrît]

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.

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 !


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

[Tellmarch]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Matthieu Brucher]

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.

[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?