[Résolu][Calc] Créateur et résolveur de Sudoku

[poissonbleu]

Avec autant de messages à votre compteur, quand allez-vous comprendre que [Basic] ne se met que lorsqu'un problème est général ?

Bonjour,

voici un document Calc qui complète les grilles de Sudoku ! (à déplacer dans la section des portions de code)
Ça ne sert à rien (l'intérêt du sudoku étant de le faire soi-même) mais c'est amusant !

Bon, mais il y a encore un "hic" : c'est un peu lent... je ne sais pas pourquoi

Au revoir

[Alain de La Chaume]

Bonjour poissonbleu

Une autre approche sur laquelle je me suis un peu amusé,
mais seulement le temps de sa création.

SudoOoku.odt

Bien coOordialement, Alain.

[poissonbleu]

Bonjour Alain de la Chaume

Je suis impressionné par ton document ! Non seulement il est plus développé que le mien, mais en plus il résout le Sudoku beaucoup plus vite.
Tu as visiblement eu quelques idées que je n'ai pas eues, comme le fait de rechercher non seulement les nombres isolés, mais aussi les paires de chiffres identiques.

Merci pour cet envoi.

[Alain de La Chaume]

Je suis impressionné par ton document !

Le code est impressionnant... mais surtout par sa taille !
Et si un pro de la prog met le nez dedans il aura certainement quelques soupirs et quelques "pffff !"
Mais bon, quand j'ai du temps à tuer (en attendant qu'il se venge), je préfère ça à la télé.

Bien coOordialement, Alain.

[poissonbleu]

Bonjour Alain,

Je me rends compte que ton document présente une certaine tare : il faut d'abord enregistrer des grilles incomplètes puis les compléter sur OOo (en se faisant éventuellement aider par l'ordinateur).

Pour ce qui est de résoudre, le code marche très bien, mais par contre, je ne pense pas que quelqu'un se donnera le mal de recopier, par l'intermédiaire de ton document, toutes les 50 grilles du cahier de Sudoku, pour l'intérêt de les faire sur OpenOffice ! Il serait donc intéressant d'écrire un code qui puisse fabriquer lui-même des grilles incomplètes (mais il faut, bien sûr, qu'elles aient une solution). D'ailleurs, je pense que cela serait possible.

L'idée serait la suivante : insérer progressivement des chiffres choisis au hasard à des positions aléatoires sur le plateau en étudiant les possibilités restantes à chaque chiffre inséré, pour éviter des situations insolubles, et répéter cette opération jusqu'à ce qu'il n'y ait plus qu'une seule solution possible, puis ajouter éventuellement quelques chiffres pour que le puzzle soit plus facile à résoudre.

Je vais donc voir ce que je peux faire, en m'appuyant sur ton fichier.
Merci encore pour cette contribution.

[Alain de La Chaume]

Salut poissonbleu

Je me rends compte que ton document présente une certaine tare

Ouais ! Normal puisque je suis un peu taré... aussi !

il faut d'abord enregistrer des grilles incomplètes

Oui, ça consiste à enregistrer le problème d'une grille avant de le résoudre.

puis les compléter sur OOo (en se faisant éventuellement aider par l'ordinateur).

Oui, on peut faire ça tout seul comme un grand (une grande), ou se faire aider.

je ne pense pas que quelqu'un se donnera le mal de recopier,

Ça, je m'en contre-fiche puisque je n'ai rien à vendre.

Il serait donc intéressant d'écrire un code qui puisse fabriquer lui-même des grilles incomplètes

Les maths ne sont pas ma tasse de thé.
Un algorithme pour créer des grilles, ça doit exister et peut-être se trouver sur le net, mais ça ne m'intéresse pas de recopier du code. Si le cœur vous en dit... Y'a qu'à... !

Bien coOordialement, Alain.

[poissonbleu]

Bonjour,

Ouais ! Normal puisque je suis un peu taré... aussi !

Bien sûr que non ! J'ai employé "tare" pour dire "problème", sans aucune signification péjorative.

Les maths ne sont pas ma tasse de thé.

Je crois qu'il ne s'agit pas vraiment de maths. Je ne compte pas recopier de code du Web, mais juste essayer par moi-même à partir de ton code.

[Churay]

Bonsoir,

Sujet passionnant...

Si on attaque le problème en brute-force qui permettrait, abordée différemment de la résolution d'une grille donnée en partie, de produire toutes les grilles valides : il a été établi que c'est de l'ordre de 6.67 x 10²¹...
On se lance dans ce que j'appelle le hard fun et on se doute et qu'il vaut mieux optimiser ce qui se trouve au coeur de la boucle infernale...

Le problème de savoir s'il existe une solution pour une grille de sudoku est classé NP-complet.
En version simplifiée :
Il existe peut-être une méthode simple pour trouver efficacement s'il existe une solution pour une grille de sudoku : mais elle n'est pas connue à ce jour.
Ce qui est rassurant, c'est qu'il n'existe pas non plus de démonstration que ce soit impossible...

La question qui se pose alors est : comment optimiser ?

Il semblerait que les résolveurs, un tant soit peu performants, s'appuient sur le backtracking (retour légèrement en arrière).
La récursivité est donc de mise.

Donald E. Knuth a publié l'algorithme X, qui s'implante avec des techniques de liste doublement chaînées (dancing links) et qui se révèle efficace pour ce genre de traitement.

Je crois qu'il ne s'agit pas vraiment de maths.

Effectivement, mais on s'approche sérieusement de l'informatique théorique...


www-cs-faculty.stanford.edu/~uno/index.html
arxiv.org/abs/cs/0011047
en.wikipedia.org/wiki/Knuth%27s_Algorithm_X

plop plop a publié un cours sympa sur openclassrooms qui devrait t'intéresser, dont le titre est Le backtracking par l'exemple : résoudre un sudoku, qui plus est en français

[joel275]

Bonjour,

on peut aussi partir de grilles toutes faites et les modifier soit:

-->en permutant les nombres de 1 à 9 dans cette grille (par exemple échanger le 2 et le 7 partout dans une grille)
--> en permutant des paquets de 3 lignes
--> en permutant des paquets de 3 colonnes
--> en échangeant les nombres par symétrie par rapport à l'une ou l'autre diagonale de la grille (qui ont pour effet d'échanger les lignes et les colonnes).
On peut combiner à loisir ces transformations pour en obtenir d'autres.

Je ne suis pas sûr que les grilles ainsi obtenues soient toutes différentes, ni qu'elles finissent par épuiser toutes les solutions possibles, mais ça devrait occuper un amateur, même monomaniaque, pendant plusieurs vies. Je ne sais pas non plus quelle influence ont ces manipulations sur la difficulté d'une grille non entièrement remplie. A vue de nez, je dirais que la difficulté ne change pas.

A plus,
Joël

[Alain de La Chaume]

Bonjour tout le monde

Tout cela est très intéressant, bien que débordant du sujet original
[Calc] Résolveur de Sudoku

Vu la tournure de ce fil, je propose que l'auteur en modifie le titre pour
[Calc] Créateur et résolveur de Sudoku

Et même si "'il ne s'agit pas vraiment de maths" (sic poissonbleu),
comme je suis davantage Lettres que Chiffres
je vais continuer à suivre ce sujet, mais en spectateur.

Bien coOordialement, Alain.

[poissonbleu]

Bonjour à tous !

Merci beaucoup pour vos réponses. Je ne réalisais pas que ce serait tellement compliqué de résoudre une grille de sudoku...

Il existe peut-être une méthode simple pour trouver efficacement s'il existe une solution pour une grille de sudoku : mais elle n'est pas connue à ce jour.

Effectivement, car ni le code d'Alain ni le mien ne sont capables de résoudre la grille suivante :

tz.jpg

qui a pourtant bien une solution. Je me demande où est le problème...

Merci à Churay pour tous ces liens intéressants.
Je me demande si je vais encore creuser le problème...

Conformément au conseil d'Alain de la Chaume, je vais changer le titre.

Encore merci pour vos conseils.
Au revoir

[Churay]

Bonjour,

Effectivement, car ni le code d'Alain ni le mien ne sont capables de résoudre la grille suivante :
qui a pourtant bien une solution. Je me demande où est le problème...

Selon la complexité de la grille, des algos différents peuvent donner ou non une solution, dans des temps qui peuvent être, eux aussi, significativement différents.

Concernant ta grille, il existe plusieurs solutions, dont celle-ci :

Sudoku_PoissonBleu.png

Pour en revenir à la notion d'approche mathématique, en voici une, agrémenté d'un source C++ qui me parait plus que performant :

• en 2 mn 36 s, résolution de 50 grilles de poids 17, soit les plus difficile à résoudre.

Deux autres algos (un linéaire, un utilisant le backtraking). L'implémentation est faite en CAML.

[poissonbleu]

Bonjour,

merci à Churay pour ses explications.
Après quelques essais, je me suis rendu compte que cet algorithme de génération de Sudoku est effectivement plus complexe que prévu...
Si donc je trouve le courage de le développer, j'ouvrirai un nouveau fil.

Je clos donc le sujet.