architecture, sudoku et "p=np?" ?

[Noress]

Bonjour,

En simple lecteur de vulgarisation mathématique, en essayant de comprendre la question p=np, le problème du sudoku généralisé m'a interpellé. Habitué à travailler sur Tableur dans des contraintes de taille des fichiers, j'y ai imaginé une sorte de modèle architectural (mais très précise) qui tient sur une seule feuille.
Pour le sudoku, par rapport à une famille s₁ qui englobe 9! grilles complètes, quelque soit la matrice creuse qu'on présente, l'architecture dit oui si une solution est dans s₁, et non si une solution n'est pas dans dans s₁.
Cette architecture peut s'étendre à de plus grandes grilles. Pour une taille de 16*16 par exemple, la famille comptera 16! grilles complètes, etc...

Cette modélisation comporte trois caractéristiques peut-être importantes.
D'abord, le modèle complète la grille sans utiliser de calcul et, peut-être que la contrainte de la complexité ne se pose pas dès lors qu'on est dans un temps d'exécution de non-calcul.
Ensuite, un paramétrage indique V ou F quand à la solution dans s₁, et là, je ne peux pas faire sans calcul (pour moi c'est impossible).
Enfin, cette modélisation n'utilise aucune base de données.

Aussi, selon vous, est-ce que cela présente un intérêt, c'est-à-dire, est-ce utile de poursuivre ?
Enfin, si cela présente intérêt, lorsqu'on présente une matrice creuse et que le modèle répond V ou F quand à la solution dans s₁, peut-il y avoir un lien avec ce qu'on appelle le problème de la décision ?

Merci pour votre temps,
Cordialement Noress.
-----

[Tryss2]

Je n'ai pas compris : c'est quoi ta famille de 9! grilles?

[Noress]

Bonjour,

Je n'ai pas compris : c'est quoi ta famille de 9! grilles?

C'est un ensemble de solutions incomplètes (ESI).
Il est vrai, j'ai utilisé "famille" car dans ces ESI, à partir d'une seule grille complète on modélise l'équivalent de 9! grilles complètes.
Je ne suis en effet pas certain de pouvoir parler de famille.

[manbruce]

Le problème du sudoku est : étant donné un remplissage partiel d'une grille n2×n2, est-il possible de la compléter en une grille « légale » ? La question de la classe de complexité porte sur le temps d'exécution du meilleur algorithme de résolution possible en fonction de n.

La classe P est celle des problèmes de décision (dont la réponse est « oui » ou « non ») pour lesquels il existe un algorithme dont le temps d'exécution est polynomial en la taille du problème (ici, n). La classe NP (pour “nondeterministic polynomial” et pas « non polynomial ») est celle des problèmes de décision pour lesquels on peut valider une réponse fournie par un oracle en temps polynomial. Il ne devrait pas surprendre que tout problème P est automatiquement NP.

Pour le sudoku, il est à peu près évident qu'on peut vérifier en temps polynomial si une grille complète est 1) une extension de la grille de départ et 2) légale. Pour le deuxième point, il suffit de parcourir les n2 lignes, les n2 colonnes et les n2 blocs ; pour chaque rangée ou bloc, on vérifie (par exemple en parcourant la rangée ou le bloc une fois pour chacun des n2 chiffres pour vérifier qu'il apparaît, ce qui prend un temps majoré par n2×n2 fois une constante) : 3n2 rangées-blocs engendrant n4 tests au plus, cela fait 3n6 tests. (Il y a sans doute moyen d'être plus habile et je me suis peut-être planté dans les puissances.) Cela justifie que le problème de sudoku est dans la classe NP.

Il y a mieux : le sudoku est NP-difficile. Cela signifie qu'il est aussi difficile que n'importe quel problème de la classe NP. Autrement dit, si on a un problème de la classe NP de taille n, on peut coder un sudoku en temps polynomial en n de sorte que la solution de ce problème de sudoku donne, en temps polynomial à nouveau, une solution du problème initial. Ainsi, à un polynôme en la taille près (qui doit pouvoir apparaître comme facteur), le temps d'exécution du meilleur algorithme de résolution de n'importe quel problème NP n'est pas plus grand que celui du sudoku.

La conséquence, c'est que si on montre que le problème des sudokus est dans la classe P, c'est-à-dire si on produit un algorithme qui résout le problème en temps polynomial, alors on sait résoudre tous les problèmes NP en temps polynomial. Autrement dit, les classes P et NP coïncident. À ce jour, presque aucun informaticien n'y croit.

(Il y a de bonnes et de mauvaises raisons, je ne connais que les mauvaises... D'une part, la difficulté que l'on rencontre est une indication négative : même si on explore beaucoup de voies, il est toujours plus facile de faire quelque chose que de prouver que c'est impossible (cf. la résolution des équations de degré ≥5, la quadrature du cercle ou la trisection de l'angle, dont la preuve d'impossibilité a été produite bien longtemps après que les gens sérieux se sont convaincus que les problèmes étaient impossibles). Autrement dit, « s'il existait un algorithme, on l'aurait trouvé depuis qu'on travaille sur ces problèmes. » D'autre part, entre P et NP, les informaticiens ont construit la « hiérarchie polynomiale », une famille infinie de classes de complexité intermédiaires entre P et NP ; si on avait P=NP, cette hiérarchie s'effondrerait (tout serait P), ce à quoi les gens ne croient pas.)

[A voir en vidéo sur Futura]

[Deedee81]

Salut,

Il y a mieux : le sudoku est NP-difficile

Je suis fort surpris que le sudoku soit dans la classe NP-complet (NP-difficile) vu la manière dont je les résous. Mais je n'ai pas vérifié strictement sur les algos.

Tu as un lien sur une démonstration que le sudoku serait dans la classe NP-complet ?

[minushabens]

Je suis fort surpris que le sudoku soit dans la classe NP-complet (NP-difficile) vu la manière dont je les résous.

mais tu les résous toujours pour la même valeur de n (9). Essaie de résoudre un sudoku à 974169 lignes et 974169 colonnes et on en reparlera.

[Noress]

Bonjour,

mais tu les résous toujours pour la même valeur de n (9). Essaie de résoudre un sudoku à 974169 lignes et 974169 colonnes et on en reparlera.

Etendre le modèle évoqué en post 1 à un sudoku d'une telle taille serait un immense travail.
Cdt

PS : on serait dans des familles qui comptent 974 169!, c'est monstrueux !

[Tryss2]

Donc en fait, si j'ai bien compris, pour résoudre le problème de taille n, il faut générer n! grilles?

Donc on ne serrait clairement pas dans le cadre d'un algorithme en temps polynomial

[Noress]

Donc en fait, si j'ai bien compris, pour résoudre le problème de taille n, il faut générer n! grilles?

Donc on ne serrait clairement pas dans le cadre d'un algorithme en temps polynomial

Peut-être et en même temps la modélisation de n! grilles permet me semble-t-il de résoudre efficacement un nombres de matrices creuses arbitrairement grand à en croire Marcus du Sautoy dans son dernier bouquin ("Le mystère des nombres", en page 254 chez Folio) où il précise :
"Trouver un programme efficace pour résoudre des sudokus arbitrairement grands est un problème NP-complet. Parfois lorsqu'il s'agit de sudokus difficiles, il vous faut émettre des suppositions en fonction des implications logiques qu'elles engendrent ; il ne semble pas exister de moyen de deviner astucieusement, il faut essayer des séries de suppositions jusqu'à ce que l'une d'entre elles vous oriente vers un réponse satisfaisante."
Et comme mon modèle ne contient pas de calcul pour la résolution, cela m'interroge.

Edit : attention le modèle ne résout pas le problème quelque soit la matrice creuse. Le modèle ne répond que dans le cadre d'un ensemble de solution incomplète.

[minushabens]

quel est le rapport entre les matrices creuses et le sudoku?

[Noress]

quel est le rapport entre les matrices creuses et le sudoku?

C'est pour distinguer l'énoncé du sudoku, c'est-à-dire la grille partiellement remplie de la grille complète.

[Noress]

Bonjour et merci,

Le problème du sudoku est : étant donné un remplissage partiel d'une grille n2×n2, est-il possible de la compléter en une grille « légale » ? La question de la classe de complexité porte sur le temps d'exécution du meilleur algorithme de résolution possible en fonction de n.

La classe P est celle des problèmes de décision (dont la réponse est « oui » ou « non ») pour lesquels il existe un algorithme dont le temps d'exécution est polynomial en la taille du problème (ici, n). La classe NP (pour “nondeterministic polynomial” et pas « non polynomial ») est celle des problèmes de décision pour lesquels on peut valider une réponse fournie par un oracle en temps polynomial. Il ne devrait pas surprendre que tout problème P est automatiquement NP.

Pour le sudoku, il est à peu près évident qu'on peut vérifier en temps polynomial si une grille complète est 1) une extension de la grille de départ et 2) légale. Pour le deuxième point, il suffit de parcourir les n2 lignes, les n2 colonnes et les n2 blocs ; pour chaque rangée ou bloc, on vérifie (par exemple en parcourant la rangée ou le bloc une fois pour chacun des n2 chiffres pour vérifier qu'il apparaît, ce qui prend un temps majoré par n2×n2 fois une constante) : 3n2 rangées-blocs engendrant n4 tests au plus, cela fait 3n6 tests. (Il y a sans doute moyen d'être plus habile et je me suis peut-être planté dans les puissances.) Cela justifie que le problème de sudoku est dans la classe NP.

Il y a mieux : le sudoku est NP-difficile. Cela signifie qu'il est aussi difficile que n'importe quel problème de la classe NP. Autrement dit, si on a un problème de la classe NP de taille n, on peut coder un sudoku en temps polynomial en n de sorte que la solution de ce problème de sudoku donne, en temps polynomial à nouveau, une solution du problème initial. Ainsi, à un polynôme en la taille près (qui doit pouvoir apparaître comme facteur), le temps d'exécution du meilleur algorithme de résolution de n'importe quel problème NP n'est pas plus grand que celui du sudoku.

La conséquence, c'est que si on montre que le problème des sudokus est dans la classe P, c'est-à-dire si on produit un algorithme qui résout le problème en temps polynomial, alors on sait résoudre tous les problèmes NP en temps polynomial. Autrement dit, les classes P et NP coïncident. À ce jour, presque aucun informaticien n'y croit.

(Il y a de bonnes et de mauvaises raisons, je ne connais que les mauvaises... D'une part, la difficulté que l'on rencontre est une indication négative : même si on explore beaucoup de voies, il est toujours plus facile de faire quelque chose que de prouver que c'est impossible (cf. la résolution des équations de degré ≥5, la quadrature du cercle ou la trisection de l'angle, dont la preuve d'impossibilité a été produite bien longtemps après que les gens sérieux se sont convaincus que les problèmes étaient impossibles). Autrement dit, « s'il existait un algorithme, on l'aurait trouvé depuis qu'on travaille sur ces problèmes. » D'autre part, entre P et NP, les informaticiens ont construit la « hiérarchie polynomiale », une famille infinie de classes de complexité intermédiaires entre P et NP ; si on avait P=NP, cette hiérarchie s'effondrerait (tout serait P), ce à quoi les gens ne croient pas.)

Est-ce que légale signifie qu'on ne doit pas procéder à un changement de repère ?
Si c'est le cas alors mon modèle n'est pas bon.
Cdt

[Deedee81]

Salut,

mais tu les résous toujours pour la même valeur de n (9). Essaie de résoudre un sudoku à 974169 lignes et 974169 colonnes et on en reparlera.

Heu.... n'exagère pas. Si le problème était NP-complet. Déjà, un sudoku 15/15 serait irréalisable (croissance exponentielle).

Ceci dit, je n'ai pas essayé d'en résoudre un, donc comme dit ci-dessus, je suis juste surpris. Pas catégorique

Noress, merci pour la citation. Je comprend beaucoup mieux. Résoudre un sudoku (légal) donné n'est pas la mort. Par contre, construire un sudoku légal peut être beaucoup plus difficile. Il y a un problème de ce type avec un jeu très konkon : démineur. Résoudre un jeu de démineur est élémentaire (même si le hasard doit parfois intervenir quand on ne peut déduire la position des mines). Par contre, s'assurer qu'un jeu de démineur partiellement joué est légal est un problème NP-complet. Voir l'article de Jean-Paul Delahaye correspondant dans Pour La Science.

Je trouve ça intéressant. En effet, pour les apprentis P-NP-istes qui cherchent à démontrer le théorème ou le réfuter, se faire la main sur ce genre de jeu est sans doute plus parlant/concret que de résoudre le 3-sat ou le problème du voyageur du commerce.

[minushabens]

bah si le temps pour résoudre un sudoku de taille n est exp(n/10^6) alors pour n=9 ce temps est 1.000009 et pour n=15 c'est 1.000015.

[Deedee81]

bah si le temps pour résoudre un sudoku de taille n est exp(n/10^6) alors pour n=9 ce temps est 1.000009 et pour n=15 c'est 1.000015.

Oui, évidemment, faut voir le taux de l'exponentielle. Mais ça m'étonnerait quand même que ce soit aussi extrême.

[minushabens]

Moi aussi. D'ailleurs pour n= 974169 on arrive à 2.8 mais je pense qu'un sudoku de cette taille doit être réellement difficile (enfin ça dépend du nombre de cases à remplir)

[Deedee81]

Moi aussi. D'ailleurs pour n= 974169 on arrive à 2.8 mais je pense qu'un sudoku de cette taille doit être réellement difficile (enfin ça dépend du nombre de cases à remplir)

Pour là le nombre de cases est énorme. D'expérience, j'aurais tendance à penser que la résolution (je souligne pour bien distinguer du problème quoté par Noress de légalité des Sudoku qui lui doit bien être NP-complet) est en n^3 ou en n^4, dans ces eaux là. Mais ça reste intuitif.

[siltoon]

Pour démontrer la NP-complètude du jeu de sudoku, je ne pense pas dire de bêtise en disant qu'on peut réduire polynomialement ce problème à un problème de coloration de graphe (qui est NP-complet).

[Noress]

Bonjour à tous,

Je vous avoue que je ne maîtrise pas du tout la complexité et c'est encore pire pour les calculs de temps.
J'ai en fait un tout autre raisonnement que je vais tenté de vous exposer.

Soit :

TRP le temps de résolution du problème NP-complet
TVS, le temps nécessaire à la vérification de la solution
Pour un problème NP-complet et bien sûr sous condition que celui sur lequel j'ai travaillé soit NP-complet et là je ne peux que m'appuyer sur Marcus du Sautoy

Est-ce que P=NP ou est-ce que P<>NP ?
A ce jour nous somme à............................. ........................TRP>TVS
Pour que P=NP nous devons nous rapprocher de ...................TRP=TVS
Et là où ça me trouble c'est qu'il semble qu'avec le modèle (peut-être de décision) on se retrouve avec TRP<TVS. Et je dois avouer que si cela s'avère recevable alors je me retrouve devant un temps de non-calcul et c'est ce que je trouve de très troublant.
Cdt.

Edit : sauf si le raisonnement n'est pas bon.

[Deedee81]

Pour démontrer la NP-complètude du jeu de sudoku, je ne pense pas dire de bêtise en disant qu'on peut réduire polynomialement ce problème à un problème de coloration de graphe (qui est NP-complet).

La coloration, je ne sais pas, la théorie des graphes oui. Le sudoku est une forme de graphe.

Et là où ça me trouble c'est qu'il semble qu'avec le modèle (peut-être de décision) on se retrouve avec TRP<TVS.

Je n'ai pas eu le temps de creuser ce modèle, mais je comprend que ça te trouble. La résolution étant une forme de vérification, on ne saurait pas avoir TRP<TVS. Si on arrive à ça, c'est qu'il y a un bug.

[Noress]

Salut,

La coloration, je ne sais pas, la théorie des graphes oui. Le sudoku est une forme de graphe.
Je n'ai pas eu le temps de creuser ce modèle, mais je comprend que ça te trouble. La résolution étant une forme de vérification, on ne saurait pas avoir TRP<TVS. Si on arrive à ça, c'est qu'il y a un bug.

Oui Deedee, c'est très troublant et je préfère un bug parce que là, on ne peut pas avoir un temps de vérification qui croît plus vite que celui de la résolution lorsqu'on fait grandir la taille du problème.
Mais que peut-on dire si contrairement à la résolution , seule la vérification contient des calculs.

[Deedee81]

Oui Deedee, c'est très troublant et je préfère un bug parce que là, on ne peut pas avoir un temps de vérification qui croît plus vite que celui de la résolution lorsqu'on fait grandir la taille du problème.

Vu que la résolution est une vérification, alors c'est forcément un bug !

Ce qui est possible c'est évidemment de pondre un "très mauvais" algorithme de vérification qui est alors plus lent que celui de résolution. Mais cela ne signifie pas que TRP<TVS. Le TVS n'est pas défini comme étant le temps d'un algorithme particulier.

Mais que peut-on dire si contrairement à la résolution , seule la vérification contient des calculs.

Là je ne comprend pas. C'est quoi une résolution "sans calcul" ????

[Noress]

Vu que la résolution est une vérification, alors c'est forcément un bug !
Ce qui est possible c'est évidemment de pondre un "très mauvais" algorithme de vérification qui est alors plus lent que celui de résolution. Mais cela ne signifie pas que TRP<TVS. Le TVS n'est pas défini comme étant le temps d'un algorithme particulier.
Là je ne comprend pas. C'est quoi une résolution "sans calcul" ????

A partir d'un énoncé de sudoku, le modèle nous dit si oui ou non une solution est dans s₁.
Pour cela, le modèle retraite l'énoncé.
Lorsque l'énoncé de sudoku est retraité, la phase de résolution est terminée (et ici il n'y a pas de calculs).
Ensuite, l'énoncé retraité est analysé pour savoir si oui ou non il y a une solution dans s₁, c'est ce que j'appelle (et désolé si c'est faux) la vérification (et ici je ne peux pas faire sans calculs).
Et si ceci n'est pas bon ce sera le fin du fil avec mes excuses.

[siltoon]

La coloration, je ne sais pas, la théorie des graphes oui. Le sudoku est une forme de graphe.

On peut facilement représenté une grille vierge de sudoku par un graphe ou chaque case est un noeud du graphe, chaque region ("carré de 9 cases") et chaque colonne et chaque ligne est une clique de taille 9.
Pour générer une grille pleine, il suffit de générer une des 9-coloration possible de ce graphe (ou grille vierge de sudoku), ou chaque couleur représente un chiffre.

D'où mon idée que le jeu de sudoku pouvait se réduire à un problème de coloration de graphe dont on sait qu'il est NP-complet

[Deedee81]

Et si ceci n'est pas bon ce sera le fin du fil avec mes excuses.

Non, c'est peut-être moi qui suit fatigué. Tu dis le "modèle retraite l'énoncé". Je ne comprend pas. Que signifie retraiter ici ???

Pour générer une grille pleine, il suffit de générer une des 9-coloration possible de ce graphe (ou grille vierge de sudoku), ou chaque couleur représente un chiffre.

Oui, en effet.

D'où mon idée que le jeu de sudoku pouvait se réduire à un problème de coloration de graphe dont on sait qu'il est NP-complet

Attention. C'est vrai pour des graphes quelconques. Mais le jeu de sudoku correspond seulement à une catégorie particulière de graphes. Et rien ne dit que dans ce cas là c'est NP-complet !!!!

[minushabens]

Je n'ai pas eu le temps de creuser ce modèle, mais je comprend que ça te trouble. La résolution étant une forme de vérification, on ne saurait pas avoir TRP<TVS. Si on arrive à ça, c'est qu'il y a un bug.

ah tiens, pour avoir un peu joué au sudoku, je trouve que c'est beaucoup plus facile de vérifier que la grille est bien remplie que de la remplir.

[Noress]

ah tiens, pour avoir un peu joué au sudoku, je trouve que c'est beaucoup plus facile de vérifier que la grille est bien remplie que de la remplir.

En effet, il suffit de vérifier visuellement qu'elle ne présente aucun doublon par ligne, colonne et région pour savoir qu'il y aura une solution.

[Deedee81]

ah tiens, pour avoir un peu joué au sudoku, je trouve que c'est beaucoup plus facile de vérifier que la grille est bien remplie que de la remplir.

Ah oui, moi aussi. Ce n'est pas contradictoire avec ce que je disais. Résoudre la grille c'est la vérifier..... mais il existe des méthodes plus simples

Donc ce que je disais plus haut c'est qu'on ne peut pas avoir TRP < TVS. Mais on peut avoir, évidemment, TVS < TRP. Je suis persuadé que c'est le cas ici (la vérification c'est en n^2, ce qui est franchement évident, par contre je n'imagine même pas un algorithme de résolution en n^2).

Attention, on parle ici de vérification de la solution (donc de la grille remplie). Ce qui est NP-complet (si j'ai bien compris ce qui était indiqué plus haut) est la vérification de la légalité de la grille. Et la résoudre, là, ne garantit pas l'unicité de la solution par exemple (bien que de la manière dont je le résous à la main me permet de voir quand ça arrive (*), donc ça dépend des algorithmes utilisés).

On a exactement la même chose avec le bête jeu de démineur.

(*) j'ai un jeu de sudoku chez moi, il ne me génère que des grilles légales. Mais je suis déjà tombé sur des grilles avec deux solutions (ou plus) dans des journaux : là je râle

[minushabens]

ah je n'avais pas compris la notion de légalité d'une grille.

[minushabens]

j'ai un jeu de sudoku chez moi, il ne me génère que des grilles légales. Mais je suis déjà tombé sur des grilles avec deux solutions (ou plus) dans des journaux : là je râle

en principe c'est interdit. C'est même un argument que j'utilise pour résoudre certains cas difficiles.