Sudoku : résolution, génération... - Page 3

Ethaniel :
C'est exactement comme en maths où des problèmes considérés comme insolubles à un moment donné par l'intégralité des mathématiciens de la planète sont du jour au lendemain simplement résolus grâce à un tout nouveau théorème mathématique venant juste d'être découvert ...

Et donc les dits problèmes étaient en fait solubles

Tu le fais exprès ?
A posteriori, oui, mais a priori, non !!!
Qu'est-ce qui te dit que tel ou tel théorème va être démontré ou infirmé, dans le futur ?
Mais si tu veux nous faire profiter de tes dons divinatoires pour nous donner le détails des futurs théorèmes mathématiques (genre la factorisation rapide du produit de deux grands nombres premiers, je pense que ça pourrait intéresser la NSA ) et des futures techniques de sudoku, ne t'en prives surtout pas, hein !

Tu as zappé une partie du post de Sally :

Sally :
je disais que je ne vois pas pourquoi (ie il n'est pas prouvé que) dans certains cas tu serais *obligé* de faire une hypothèse (ie qu'il n'existe pas de méthode (connue ou inconnue) permettant de déterminer le résultat sans faire d'hypothèse)

Toi tu nous parles de théorèmes « considérés insolubles par la communauté des mathématiciens » et de techniques « inconnues même par les meilleurs joueurs de sudoku », ce qui ne veut en aucun cas dire qu'ils sont respectivement insolubles et inexistants, heureusement.

Tu renverses la charge de la preuve, sally dit qu'il n'est pas prouvé que des grilles insolubles sans backtracking existent, et ton contre-argument c'est en substance « prouve moi qu'elles n'existent pas ». C'est débile (s/grilles insolubles/Dieu si tu comprends pas pourquoi c'est débile)

Euh... oui, peut-être, je ne sais pas : vu l'heure, j'ai sans doute zappé les subtilités de langages, je relirai ça quand je serai un peu plus réveillé ...

Heu pour la seconde (e-sudoku) tu es sur d'avoir fait la derniere version de la grille ? non pasque le gars c'est foiré en la postant)



Et change de soft de sudoku...
J'en ai un qui est loin d'avoir toutes les méthodes listé par ton site, mais quie st capable de resoudre celui de "e-sodoku" et ce, sans passer par la methodes de nishio...

par contre utilisation des talbles de trebor, ou du "Bowman Bingo" mais ce ne sont l'un ni l'autre du "try and guess"

--- post plus bas ---

Bon un fichier texte sera plus simple :


http://godzil.free.fr/dl.php?file=/public/Grille%20eSudoku.txt


On peut récapituler en :

Heuristics used:

  11 x Bowman Bingo
  4 x Comprehensive Forcing Chains
  1 x Simple Forcing Chains
  1 x XY-Wing
  2 x Comprehensive Naked Sets
  5 x Intersection Removal
  4 x Simple Naked Sets
  6 x Pinned Squares

(heuristic me parrais mal choisis mais bon..)

(bah ce sont bien des heuristiques dans la mesure où ce sont des règles arbitraires, qui ne recouvrent pas tous les cas, et qui ont pour but d'accélérer le calcul ^^)

Et ce qu'ils appellent le "bowman bingo" pourquoi c'est pas du "try and guess" ? Je veux dire, ils mettent une valeur dont ils ne sont pas sûrs, puis après ils regardent si ça colle au bout d'un nombre d'étapes arbitrairement élevé, c'est ce que j'appellerais du "try and guess"...

C'est pas classé dans le try and guess dans les définitions de cette methode que j'ai trouvé. C'est une méthode (bcp) plus complexe que les méthodes habituelles, mais n'est pas reférencé dans les try & guess..

./60 > non mais ça je veux bien admettre que ça existe (enfin, je n'en savais rien, donc merci pour l'information ^^), après ça, on est d'accord, c'est juste qu'on ne parle pas exactement de la même chose : ce dont tu parles c'est une grille qu'on ne SAIT pas résoudre sans avoir recours au backtracking (parce qu'on n'y arrive pas), moi je mettais seulement en doute l'existence d'une grille qu'on ne PEUT pas résoudre sans avoir recours au backtracking (parce que c'est impossible).

Alors peut-être que si tu n'as pas compris de quoi je parlais c'est parce que ça te semble évident qu'une telle grille (impossible à résoudre sans backtracking quoi qu'il arrive, pour les siècles des siècles, et même par Dieu) n'existe pas ; effectivement intuitivement on a envie de dire que ça n'existe pas parce qu'il y a sûrement toujours des techniques auxquelles on n'a pas pensé (c'est précisément pour ça que je mets en doute leur existence), mais bon parfois on a des surprises, peut-être que ça existe quand même (mais il faudrait le prouver).

Sinon, je ne pense pas que tu aies fait beaucoup de maths, mais on ne considère un problème comme insoluble que quand il est *démontré* qu'il est insoluble : quand c'est juste que personne n'a réussi à le résoudre jusqu'à présent, on se contente de le considérer comme non résolu . (Bon, éventuellement, quand vraiment beaucoup de gens n'arrivent pas à le résoudre, on peut *conjecturer* qu'il est insoluble, mais on ne peut pas l'affirmer tant que ce n'est pas prouvé...) La notion de problème soluble a posteriori ou a priori n'a pas beaucoup de sens en mathématiques : un problème est soluble ou pas, après soit tu sais s'il l'est soit tu ne le sais pas, c'est tout.

D'ailleurs souvent c'est l'inverse de ce que tu dis qui se produit : on cherche pendant des siècles la solution à des problèmes qu'on pense solubles (typiquement, la quadrature du cercle ou la trisection de l'angle à la règle et au compas) et un beau jour on parvient à démontrer qu'en fait on cherchait pour rien parce que ces problèmes sont insolubles ^^

Moumou a écrit :
Tu as zappé une partie du post de Sally :

Sally :
je disais que je ne vois pas pourquoi (ie il n'est pas prouvé que) dans certains cas tu serais *obligé* de faire une hypothèse (ie qu'il n'existe pas de méthode (connue ou inconnue) permettant de déterminer le résultat sans faire d'hypothèse)

Toi tu nous parles de théorèmes « considérés insolubles par la communauté des mathématiciens » et de techniques « inconnues même par les meilleurs joueurs de sudoku », ce qui ne veut en aucun cas dire qu'ils sont respectivement insolubles et inexistants, heureusement.
Tu renverses la charge de la preuve, sally dit qu'il n'est pas prouvé que des grilles insolubles sans backtracking existent, et ton contre-argument c'est en substance « prouve moi qu'elles n'existent pas ». C'est débile (s/grilles insolubles/Dieu si tu comprends pas pourquoi c'est débile)

Ça y est, c'est bon, je viens enfin de comprendre ...
Sally parle de « l'existence de grilles qui, intrinsèquement, nécessitent du backtracking », et moi je parle de « l'existence de grilles qui, en l'état actuel des connaissances, nécessitent du backtracking ».
Jamais je n'ai voulu parler du premier cas, d'autant plus que parler de l'existence de ce genre de chose (grille nécessitant intrinsèquement du backtracking (GNIB), Dieu, licorne invisible et immatérielle, cygne noir de Popper, toussah ) est vérifiable mais non réfutable, donc c'est non scientifique.
Et encore, vérifiable, même pas vraiment, puisque ça supposerait d'être sûr que l'on dispose de l'intégralité des techniques possibles, ce qui est loin d'être le cas .

Sally a écrit :
./60 > non mais ça je veux bien admettre que ça existe (enfin, je n'en savais rien, donc merci pour l'information ^^), après ça, on est d'accord, c'est juste qu'on ne parle pas exactement de la même chose : ce dont tu parles c'est une grille qu'on ne SAIT pas résoudre sans avoir recours au backtracking (parce qu'on n'y arrive pas), moi je mettais seulement en doute l'existence d'une grille qu'on ne PEUT pas résoudre sans avoir recours au backtracking (parce que c'est impossible).

Oui, voilà, c'est justement ce que je viens de dire !
Et ce paragraphe, c'est justement ce que je viens de lire : pas réveillé, aujourd'hui, le petit Ethaniel ...

Sally a écrit :Alors peut-être que si tu n'as pas compris de quoi je parlais c'est parce que ça te semble évident qu'une telle grille (impossible à résoudre sans backtracking quoi qu'il arrive, pour les siècles des siècles, et même par Dieu) n'existe pas ; effectivement intuitivement on a envie de dire que ça n'existe pas parce qu'il y a sûrement toujours des techniques auxquelles on n'a pas pensé (c'est précisément pour ça que je mets en doute leur existence), mais bon parfois on a des surprises, peut-être que ça existe quand même (mais il faudrait le prouver).

Ah non, je n'ai jamais dit que les GNIB existaient, mais je n'ai jamais dit non plus qu'elles n'existaient pas !!!

Mais revenons-on au bout de phrase mal compris qui nous a lancé là-dedans :

Sally a écrit :
Si la solution est unique, je ne comprends pas comment tu peux être obligé de mettre un chiffre au hasard

À mon humble avis (et à mon humble intuition), je ne vois aucune corrélation entre l'unicité de la solution et la nécessité de backtracker ...

Sally a écrit :
Sinon (je dévie un peu de la question ^^) la méthode de l'hypothèse à le défaut de ne pas prouver que la solution est unique, justement (on fait confiance au concepteur, ok, mais moralement c'est pas très satisfaisant). Enfin sauf si tu explores tout l'arbre, évidemment, mais bon s'il est grand... .

Certes.
Et pourtant, il existe quelques techniques (que j'ai découvertes hier) qui utilisent cette hypothèse d'unicité pour avancer !
Oh, et puis au passage :

J'ai écrit en ./57 :
L'hypothèse nécessaire autorisant le backtracking est que la solution d'une grille est unique.

Sally a écrit :
Sinon, je ne pense pas que tu aies fait beaucoup de maths, mais on ne considère un problème comme insoluble que quand il est *démontré* qu'il est insoluble : quand c'est juste que personne n'a réussi à le résoudre jusqu'à présent, on se contente de le considérer comme non résolu . (Bon, éventuellement, quand vraiment beaucoup de gens n'arrivent pas à le résoudre, on peut *conjecturer* qu'il est insoluble, mais on ne peut pas l'affirmer tant que ce n'est pas prouvé...) La notion de problème soluble a posteriori ou a priori n'a pas beaucoup de sens en mathématiques : un problème est soluble ou pas, après soit tu sais s'il l'est soit tu ne le sais pas, c'est tout.
D'ailleurs souvent c'est l'inverse de ce que tu dis qui se produit : on cherche pendant des siècles la solution à des problèmes qu'on pense solubles (typiquement, la quadrature du cercle ou la trisection de l'angle à la règle et au compas) et un beau jour on parvient à démontrer qu'en fait on cherchait pour rien parce que ces problèmes sont insolubles ^^

Effectivement, je n'ai pas beaucoup de notions dans cette branche mathématique (metamathématique, suis-je tenté de dire ) où, au lieu de démontrer un théorème, on cherche à savoir s'il peut ou non être démontré, sans dire comment si c'est le cas...
La seule chose que je connais, c'est que Gödel et Cohen ont démontré chacun une moitié de l'indécidabilité de l'hypothèse du continu (aleph₀, aleph₁, Cantor, toussah ), rien de plus.

Godzil a écrit :Heu pour la seconde (e-sudoku) tu es sur d'avoir fait la derniere version de la grille ? non pasque le gars c'est foiré en la postant)

Non, je ne l'ai pas faite : j'étais encore au boulot, donc voilà ...

Godzil a écrit :
Et change de soft de sudoku...J'en ai un qui est loin d'avoir toutes les méthodes listé par ton site, mais quie st capable de resoudre celui de "e-sodoku" et ce, sans passer par la methodes de nishio...

C'était à Noël dernier, je venais juste de découvrir le sudoku, je cherchais un solveur en ligne pour la fameuse grille que j'ai mise dans “J'aime pas”, donc je n'ai pas cherché bien loin.
Par contre, je viens de chercher à nouveau ce solveur en ligne, je l'ai retrouvé, et le nombre de techniques utilisées par le programme, en comptant les 7 de bases tellement de base qu'on ne peut même pas les désactiver, vaut plus du double de ce qu'il y avait à Noël !
Donc si ça se trouve, la grille “impossible” de Noël est peut-être maintenant facilement résolue par ce solveur ...

Godzil a écrit :par contre utilisation des talbles de trebor, ou du "Bowman Bingo" mais ce ne sont l'un ni l'autre du "try and guess"

Le “Bowman Bingo” faisant intervenir, si j'ai bien compris, à la fois plusieurs candidats (== chiffres potentiels d'une case donnée) et plusieurs emplacements (== cases potentielles d'un chiffre donné) avec interactions entre eux, donc en remplissant temporairement la grille, j'appelle ça clairement du "try & guess" / "backtracking" / "essai & erreur", et c'est d'ailleurs classé à "Trial and Error" par le solveur en ligne dont j'ai parlé.
Par contre, le Nishio, perso, je n'appelle pas ça du backtracking, puisque les candidats sont analysés un par un sans interaction entre eux, donc sans avoir besoin de remplir temporairement la grille : et si on considère que le Nishio est du backtracking, alors ce que j'appelle la "compression" (technique générique regroupant en fait les jumeaux et les interactions entre blocs) et qui est considérée par tout le monde comme étant “de base” est également du backtracking, puisque ce n'est rien de plus que du Nishio avec quelques conditions supplémentaires qui facilitent grandement son repérage à l'œil nu.
D'ailleurs, je ne suis pas le seul à refuser le classification du Nishio en essai/erreur :

http://www.setbb.com/phpbb/viewtopic.php?t=11 :
Some people regard the rule as controversial because it relies upon
reductio ad absurdum - however, the rule cannot be classified astrial-and-error because it always leaves the grid in a valid state.

Et sinon, pour les tables de Trebor, la seule chose que j'ai trouvée est que ce n'était pas faisable de tête et nécessitait un ordi poubelle, une technique de résolution DOIT être possible de tête, puisqu'une grille de sudoku doit par définition être soluble à la main...


Sinon, question intéressante : où se situe la limite pour qualifier ou non une technique de backtracking ?
Le fait de remplir temporairement la grille ? Et si quelqu'un a une très bonne mémoire et réussit une grille sans rien écrire ?
Le fait de devoir se servir de l'hypothèse d'unicité de la solution ? Ça pourrait être une très bonne définition, mais qui oserait actuellement qualifier cette technique de backtracking ?
Autre chose ?
Huhu , en voilà une question qu'elle est bien !

Ethaniel :

Sally a écrit : Alors peut-être que si tu n'as pas compris de quoi je parlais c'est parce que ça te semble évident qu'une telle grille (impossible à résoudre sans backtracking quoi qu'il arrive, pour les siècles des siècles, et même par Dieu) n'existe pas ; effectivement intuitivement on a envie de dire que ça n'existe pas parce qu'il y a sûrement toujours des techniques auxquelles on n'a pas pensé (c'est précisément pour ça que je mets en doute leur existence), mais bon parfois on a des surprises, peut-être que ça existe quand même (mais il faudrait le prouver).

Ah non, je n'ai jamais dit que les GNIB existaient, mais je n'ai jamais dit non plus qu'elles n'existaient pas !!!

Je sais, je disais juste que *peut-être* que tu pensais évident qu'elles n'existent pas et que c'était pour ça que tu n'avais pas compris de quoi je parlais, mais ça n'était qu'une hypothèse ^^

Ethaniel :

Sally a écrit :
Si la solution est unique, je ne comprends pas comment tu peux être obligé de mettre un chiffre au hasard

À mon humble avis (et à mon humble intuition), je ne vois aucune corrélation entre l'unicité de la solution et la nécessité de backtracker ...

Ben, c'est précisément cette phrase que j'ai explicitée plus tard : "je ne vois pas pourquoi" ou "je ne comprends pas comment" ça veut juste dire que je doute fortement de l'existence des GNIB et que celle-ci n'est pas prouvée. Quant au lien avec le fait que la solution soit unique, ben c'est tout simplement que si la solution *n'est pas* unique il y a forcément un moment où un autre où tu vas devoir choisir arbitrairement comment remplir une case (et éventuellement backtracker si tu veux retrouver *toutes* les solutions), donc la question ne se pose que dans le cas d'une solution unique.

Ethaniel :
l'existence de ce genre de chose (grille nécessitant intrinsèquement du backtracking (GNIB), Dieu, licorne invisible et immatérielle, cygne noir de Popper, toussah )

Tu mets dans le même panier des choses de natures différentes : une GNIB est un objet mathématique dont on peut a priori donner une description précise, et il est tout à fait vraisemblable qu'il y ait moyen de prouver leur existence ou leur inexistence, même si ça n'est pas certain. Et les critères de scientificité d'une théorie sont pour les sciences naturelles (au sens le plus large du terme, les sciences du réel si tu veux), pas pour les mathématiques qui sont de nature différente. La réfutabilité ne veut rien dire si tu ne parles pas de la réalité.

Ethaniel :

Jamais je n'ai voulu parler du premier cas, d'autant plus que parler de l'existence de ce genre de chose (grille nécessitant intrinsèquement du backtracking (GNIB), Dieu, licorne invisible et immatérielle, cygne noir de Popper, toussah ) est vérifiable mais non réfutable, donc c'est non scientifique.
Et encore, vérifiable, même pas vraiment, puisque ça supposerait d'être sûr que l'on dispose de l'intégralité des techniques possibles, ce qui est loin d'être le cas .

Ben pourquoi serait-ce invérifiable et irréfutable ? Ça l'est peut-être en l'état actuel de nos connaissances, mais rien ne dit que ça le sera toujours ...

Là, comme ça, à 4h du mat' (juste une #excuse# au cas où je m'apprête à raconter une connerie de plus ), je dirais que pour vérifier et/ou réfuter l'existence des GNIB, il faudrait avoir sous la main l'intégralité des techniques non assimilées à du backtracking.
Or :[ul][li]Question 1 : peut-on formaliser les techniques en un langage précis permettant alors de d'énumérer une par une toutes les techniques potentielles ? Si oui, sont-elles en nombre fini ?
Équivalent informatique : tout programme peut être assemblé sur archi x86, et je peux énumérer tous les programmes Asm x86 de taille 1 octet (il y en a 256), tous les programmes de taille 2 octets (il y en a 256², mon préféré est EBFE ), etc. jusqu'à, mettons, les programmes de taille 65536 octets (ce qui permet d'avoir un nombre fini de programmes différents), puis j'analyse un par un chaque programme pour voir ceux qui ne servent à rien, ceux qui dessinent un point à l'écran, ceux qui décrivent dans un formalisme donné une technique sans backtracking, ceux qui jouent la Flûte Enchantée de Mozart, ceux qui trouvent 42, etc.
[li]Question 2 (déjà posée) : qu'est-ce qui définit le caractère backtracking d'une technique ? Peut-être que la formalisation de la question 1 pourrait y répondre (équivalent informatique : tous les programmes de 42053 octets avec 0x2A en 14^e octet décrivent une technique sans backtracking), mais en attendant, les gens ne sont même pas d'accord pour dire si le Nishio est du backtracking ou non ...[/ul]

Ben le problème n'est pas formalisable car si on accepte n'importe quel algorithme formel alors on accepte l'algorithme trivial qui à chaque grille associe sa solution en la recherchant dans la base de données de toutes les solutions de toutes les grilles de sudoku (qui ne backtracke évidemment pas). Mais bon c'est pas parce que c'est informel qu'on n'a pas le droit d'en parler

Ethaniel :
Là, comme ça, à 4h du mat' (juste une #excuse# au cas où je m'apprête à raconter une connerie de plus ), je dirais que pour vérifier et/ou réfuter l'existence des GNIB, il faudrait avoir sous la main l'intégralité des techniques non assimilées à du backtracking. Or :[ul][li]Question 1 : peut-on formaliser les techniques en un langage précis permettant alors de d'énumérer une par une toutes les techniques potentielles ? Si oui, sont-elles en nombre fini ?

Le problème est qu'on manipule des grilles de taille bornée, donc c'est un peu impossible à définir dans ce contexte-là sans accepter la solution triviale de Moumou. Si en revanche on fait varier la taille des carrés et qu'on l'appelle N, on peut par exemple dire "une technique est un algorithme de taille polynômiale en N, utilisant une mémoire logarithmique en N" (c'est peut-être foireux comme définition, je ne sais pas, mais au moins ça exclut l'exemple de moumou qui est de taille exponentielle en N, et ça doit inclure pas mal d'algorithmes classiques)

Équivalent informatique : tout programme peut être assemblé sur archi x86, et je peux énumérer tous les programmes Asm x86 de taille 1 octet (il y en a 256), tous les programmes de taille 2 octets (il y en a 256², mon préféré est EBFE ), etc. jusqu'à, mettons, les programmes de taille 65536 octets (ce qui permet d'avoir un nombre fini de programmes différents), puis j'analyse un par un chaque programme pour voir ceux qui ne servent à rien, ceux qui dessinent un point à l'écran, ceux qui décrivent dans un formalisme donné une technique sans backtracking, ceux qui jouent la Flûte Enchantée de Mozart, ceux qui trouvent 42, etc.

Euh, si tu es capable de me donner un programme qui calcule le nb de programmes de moins de 256 octets qui renvoient 42 (même s'il met des milliards de siècles à le calculer), je veux bien te donner 1 million de dollars

tu penses qu'il est impossible de trouver tous les programmes de moins de 256 octets qui ne terminent pas ?

1. je ne dis pas que c'est impossible, au contraire c'est un nombre de 256 bits que l'on peut effectivement calculer, par contre je dis que l'écriture d'un programme qui le calculerait présente tellement d'obstacles que la preuve de correction du programme sera obligatoirement hyper, hyper, hyper longue ^^ (et elle est très significativement plus compliquée que la preuve pour 192 octets, qui elle-même est significativement plus compliquée que la preuve pour 128 octets, etc...)
2. ça dépend évidemment de l'encodage, mais pour n'importe quel encodage "raisonnablement expressif" ça me paraît évident qu'il faut réussir à démontrer tout un tas de théorèmes de maths compliqués et à résoudre des conjectures non résolues :

foreach ((x,y,z,n) in (N*)^4)
  if (n>2 && x^n == y^n+z^n)
    break;

(ne s'arrête pas à cause du théorème de Fermat)

foreach (x>0) {
  bool ok = false;
  foreach (0<a<x && 0<b<x)
    if (x==a+b && isprime(a) && isprime(b))
      ok = true;
  if (iseven(x) && x>2 && !ok)
    break;
}

(s'arrête ssi la conjecture de Goldbach est fausse)

bon et si tu limites l'occupation mémoire à 256 octets ?

faudra se lever tôt pour exécuter ne serait-ce qu'un seul programme pendant 2^2048 cycles, mais c'est déjà plus raisonnable, oui

boah, il faudra juste 2^4096 cycles et 2^2048 bits de mémoire pour trouver tous les programmes de moins de 256 octets qui répondent 42 en occupant moins de 256 octets de mémoire, facile quoi

(2^4096 bits de mémoire si on accepte le code self-modifiable)

Pour ta grille du #0 : http://www.e-sudoku.fr/forum/viewtopic.php?t=797

Le point central de la resolution est (Alternating Inference Chains) : http://www.scanraid.com/AdvanStrategies.htm#AIC

Tout le reste est des trucs classiques (dont un ou deux XWings & co)