Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
420 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Algorithmes et sudoku

Envoyé par Homo Topi 
Algorithmes et sudoku
l’an passé
Je pense qu'on a tous déjà fait un sudoku. Là, j'en ai refait un pour la première fois depuis longtemps, et mon cerveau s'est mis à poser des questions à la chaîne.

Le truc que je trouve intéressant, c'est que dès qu'on tombe sur une grille de sudoku, c'est écrit dans les consignes que la grille est garantie d'être résoluble, et de plus, de manière unique. Et je n'ai pas l'impression que c'est facile de démontrer l'unicité de la solution d'une grille "finissable" de sudoku.

Pour justifier qu'elle est garantie d'être résoluble d'au moins une manière, je pense que c'est évident : on part d'une grille complète qui respecte les règles, puis on retire des chiffres. La grille complète dont on est parti est une solution, et je pense que c'est évident qu'on peut effectivement trouver cette solution. Peut-être qu'il faudra tester pendant des heures, mais c'est possible de la retrouver.

Par contre, ce qui m'intéresse beaucoup plus, c'est l'unicité de la solution. Je suppose que les créateurs de grilles de sudoku partent d'une grille complète, et ont une manière de vérifier, à chaque fois qu'ils enlèvent un chiffre, que la grille n'admet toujours qu'une seule solution. Mais comment fait-on pour tester l'unicité, informatiquement ? Il faut bien faire ça avant de proposer la grille à quelqu'un (conscience professionnelle oblige grinning smiley).

Donc, le premier algorithme dont aurait besoin un mathématicien créateur de sudokus, c'est un algorithme qui complète une grille. Ou plutôt, qui cherche toutes les manières de compléter une grille donnée. C'est mieux de faire ça comme algorithme, parce que si l'algorithme trouve plusieurs solutions, c'est que la grille de départ ne contenait plus assez de chiffres.

[Je propose un algorithme qui est garanti d'être fonctionnel, mais qui est totalement idiot et non-optimisé (par flemme de décrire un algorithme qui connait toutes les techniques) : on part de la première case libre, on y place un chiffre $x$ autorisé, puis on refait ça en boucle une tonne de fois jusqu'à avoir soit une grille complète, soit un problème. Si on a un problème, il faut recommencer du début avec la prochaine valeur possible pour $x$, et si on a trouvée une grille acceptable, on la garde en mémoire et on recommence avec $x$ jusqu'à avoir épuisé toutes les possibilités où c'est $x$ dans la permière case libre.]

Mais là, on va avoir des soucis : quel(s) chiffre(s) rajouter pour rendre la grille résoluble ? C'est quasiment certain qu'il y a plusieurs manières de faire ça, donc le mieux ça serait de toutes les trouver (mais comment ?)

Pour ne pas avoir ce genre de problème, on pourrait partir d'une grille complète, retirer un chiffre (plus ou moins au hasard), tester si la grille est encore finissable d'une seule manière, puis en retirer un autre, etc, jusqu'à tomber sur une grille qui n'a plus assez de chiffres pour avoir une solution unique. Mais là, étape par étape, il faudrait retester la résolubilité de la grille, avec le premier algorithme. Ça va devenir très long.

En question subsidiaire... partant d'une grille complétée, quel est le nombre minimal de chiffres qu'il faut laisser dedans pour qu'elle soit résoluble ? On pourrait utiliser ça pour proposer des grilles de difficulté maximale, puis rajouter des chiffres à ces grilles "minimales" pour proposer des grilles plus simples.

Tant qu'on est là... si l'idée est effectivement de partir de grilles complétées, je pense qu'on peut calculer le nombre total de grilles complétées qui existent (tiens, un problème d'algèbre et combinatoire grinning smiley). Et après, pour une grille donnée, détermier toutes les grilles "minimales" qu'on peut en tirer, puisque toutes les autres grilles sont construites sur celles-là. Pour faire ça, il faudrait trouver un algorithme... performant, de préférence, vu le nombre de tests qu'il faut faire.

Quelqu'un ici a déjà réfléchi à ces questions et saurait comment chercher ce que je propose ? Ce qui m'intéresse, dans l'absolu, c'est le raisonnement mathématique, les algorithmes mathématiques, mais s'il y a besoin de partager des programmes, je digère le Python à petites doses grinning smiley.

Je vous jure que je saurai faire de l'analyse réelle un jour !
JFS
Re: Algorithmes et sudoku
l’an passé
avatar
Bonjour,

Je suis déjà tombé sur des sudoku qui avaient 2 solutions : les 4 dernières cases pouvaient être remplies de 2 façons différentes par les 2 chifres manquants.

Cordialement
Dom
Re: Algorithmes et sudoku
l’an passé
S’il n’y a pas unicité, alors ce n’est pas une grille de sudoku. Des coquilles doivent résider dans l’algorithme de l’auteur.
Il me semble qu’un problème ouvert est de déterminer le nombre minimal de chiffres déjà déterminés pour qu’une grille soit une grille de sudoku (c’est-à-dire avec unicité).
Re: Algorithmes et sudoku
l’an passé
avatar
Il me semblait que c’était 16 ou 17.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: Algorithmes et sudoku
l’an passé
avatar
Une grille de Sudoku avec moins de 17 cases révélées n'a pas de solution unique:
[fr.wikipedia.org]

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: Algorithmes et sudoku
l’an passé
En général l'unicité c'est à une transposition près .
Dom
Re: Algorithmes et sudoku
l’an passé
Fin de partie : si j’ai bien compris c’est une conjecture sauf à croire sur parole un document Arxiv, non ?
Re: Algorithmes et sudoku
l’an passé
avatar
Dom:
Si tu as le courage de lire ce pdf (ce que je n'ai pas eu) tu découvriras surement que ce n'est pas qu'une conjecture. smoking smiley

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Dom
Re: Algorithmes et sudoku
l’an passé
Ok si ça suffit à te convaincre.

Cependant je ne me rends même pas compte du temps qu’il faudrait pour tester toutes (après avoir évité les symétries et autres permutations) les grilles à 16 révélés.


C’est peut-être mentionné dedans mais je ne lis pas l’anglais et ai autant de courage que toi winking smiley
[arxiv.org]
On y parle de la fin d’un « calcul » demandant plus de 7 millions d’heures.



Edité 2 fois. La dernière correction date de l’an passé et a été effectuée par Dom.
Re: Algorithmes et sudoku
l’an passé
J'étais à peu près certain que des matheux s'étaient déjà posés mes questions avant moi. Je pressentais aussi que ça serait sûrement compliqué comme problème... en attendant, si c'est un papier compliqué à lire, je n'aurai pas le temps de le faire là dans les prochains temps, mais ça m'a l'air intéressant. J'apprendrai sûrement plein de choses parce que je n'ai aucune idée comment commencer à chercher une solution au problème.

Merci pour vos contributions !

Je vous jure que je saurai faire de l'analyse réelle un jour !
Re: Algorithmes et sudoku
l’an passé
avatar
Bonjour,

Ca a l'air effectivement un problème difficile en toute généralité.

Par contre sur un exemple de grille auquel on aurait vidé des cases c'est faisable : les algos assez naturels pour résoudre un sudoku font du "backtracking", et on peut les implémenter pour chercher toutes les solutions. (Je ne l'ai jamais fait, je ne me rends pas compte du temps de calcul.)
Re: Algorithmes et sudoku
l’an passé
Je me demande s'il y a des "motifs" minimaux résolubles.

Dans le sens : admettons qu'on ait une grille minimale (appremment, 17 nombres donnés). Quelles sont les dispositions possibles pour ces 17 nombres pour que la grille soit effectivement finissable (d'une seule manière, comme toujours)... ces dispositions sont-elles "conjuguées" entre elles ou pas ?

C'est fou le nombre de questions que ça soulève, un sudoku grinning smiley

Je vous jure que je saurai faire de l'analyse réelle un jour !
Re: Algorithmes et sudoku
l’an passé
avatar
Homo Topi:

Sur la page Wikipedia consacrée au Sudoku, il y a une animation d'une grille à 17 cases révélées.

Je vis parce que les montagnes ne savent pas rire, ni les vers de terre chanter.(Cioran)
Re: Algorithmes et sudoku
l’an passé
Je reviens ici, ça fait un moment (déménagement, etc)

Des sudokus à 17 révélées, je suis certain d'en avoir résolu plusieurs moi-même. Ce qui m'intéresse, c'est pourquoi 17 c'est le nombre minimal garanti pour qu'il y ait une solution unique. Et si la disposition de ces 17 joue un rôle, ou si la donnée de n'importe quelles 17 cases d'un sudoku garantit qu'il soit résoluble, et ce d'une seule manière.

Les gens ont mentionné de la littérature, ici... visiblement, c'est plus compliqué que ce à quoi je m'attendais. Je lirai ça un jour, pendant des vacances ou un autre moment ou j'aurais du temps.

Je vous jure que je saurai faire de l'analyse réelle un jour !
Re: Algorithmes et sudoku
l’an passé
avatar
Tu te doutes que si un sudoku a une ligne et une colonne donnés exactement (par exemple le coin supérieur droit), je doute que le sudoku soit résoluble.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Re: Algorithmes et sudoku
l’an passé
Oui, du coup, trouver les conditions (en plus de prouver ce nombre de 17 révélées) ça m'a l'air difficile !

Je vous jure que je saurai faire de l'analyse réelle un jour !
Re: Algorithmes et sudoku
l’an passé
avatar
C'est très difficile, effectivement. Le recensement de tous les 17-uplets risque d'être très long.

On peut essayer de rendre les choses génériques, en faisant entrer des considérations de symétries. Si par exemple on constate que le 17-uplet (A1 B2 B4 B5 B7 C3 D1 E1 F8 G2 G3 H4 H5 I4 I6 I3 I9) permet de définir des grilles uniques, alors, à partir de ce 17-uplet, on peut en bâtir des milliers d'autres :
- En permutant les lignes (on peut permuter les lignes A B et C, les lignes D E F , les lignes G H I)
- En permutant les colonnes (on peut permuter les colonnes 1 2 3, les colonnes 4 5 6, les colonnes 7 8 9)
- Et en permutant lignes avec colonnes.
- Et j'oubliais, on peut aussi permuter le bloc de 3 lignes ABC avec le bloc DEF ou avec GHI., et idem pour les colonnes.

On a donc des classes d'équivalences ( tous les 17-uplets qu'on obtient à partir d'un 17-uplet donné, par des permutations de lignes ou de colonnes)
Une question préliminaire serait donc :
Combien y-a-y-il de façons de disposer 17 cases sur une grille de 9x9 . Facile.
A combien ça se réduit en prenant en compte les permutations autorisées ? Déjà, ici, Ca se complique bigrement, parce que en divisant par 6^6*2, on tombe en-dessous de la réalité.

Parmi tous les 17-uplets, Il y en a certains pour lesquels on est sur qu'ils ne conviendront pas. Par exemple, si dans mon 17-uplet, je n'ai aucune case de la 8ème ligne, ni de la 9ème ligne, on est sûr que ce 17-uplet ne convient pas.

Sur le même thème du Sudoku et du nombre de cases minimales, on peut trouver d'autres sujets d'étude.

On sait qu'il y a des grilles finales qu'on peut résoudre à partir de 17 indices. Et qu'il n'y a aucune grille qu'on peut résoudre à partir de 16 indices.
A partir d'une grille quelconque (la grille remplie, avec des chiffres de 1 à 9), y-a-t-il forcément un 17-uplet qui va permettre de résoudre cette grille ?
Peut-être que la question a déjà été solutionnée, je n'ai pas fait du tout les recherches.



Edité 1 fois. La dernière correction date de l’an passé et a été effectuée par lourrran.
Re: Algorithmes et sudoku
l’an passé
Peut-être qu'il faudrait commencer par des sudokus 4x4, tiens.

Je vous jure que je saurai faire de l'analyse réelle un jour !
Re: Algorithmes et sudoku
l’an passé
avatar
Ceux-là peuvent se bourriner.

Le café est un breuvage qui fait dormir,
quand on n’en prend pas.
-+- Alphonse Allais -+-
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 145 106, Messages: 1 444 113, Utilisateurs: 27 157.
Notre dernier utilisateur inscrit Mahamat Ali Ibrahim.


Ce forum
Discussions: 2 461, Messages: 18 164.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page