[Index Jeux] Sudoku

[Bubu]

... message inutile.

[Bubu]

J'ai eu ma période Sudoku aussi.
J'adorais ça. Quand on trouve un chiffre, on est très content, avec la petite stéréotypie qui va avec .
En plus cela fait travailler les méninges !

J'ai fait un petit logiciel pour Windows, (je l'ai fait quand j'étais étudiant. Je garde le projet sur Cloud, mais après relecture du code, je ne comprends plus rien ! ) qui génère des grilles avec plusieurs niveaux de difficulté, qui permet de mettre les chiffres éventuels en petit dans les cases, et il résout toute grille, même AI escargot, créée par un mathématicien, la grille la plus difficile connue. Il y a du challenge : je n'ai jamais résolu une seule grille en "très difficile". A ce niveau, on est obligé de choisir une possibilité, et d'essayer de résoudre la grille. Si on arrive à une contradiction, il faut revenir en arrière et choisir une autre possibilité. C'est plutôt pénible et ardu. Et pourtant c'est l'algorithme utilisé par les logiciels.

Je le mets dans le message :

SudokuW.exe.txt

Enlevez l'extension txt. Pour un ordi à jour normalement il suffit de double cliquer sur l'exe. Si jamais on vous dit qu'il manque une dll, installez les redistribuables C++. Taille du truc insignifiante. Par contre si vous ne parvenez pas à le trouver, faîtes moi signe, et je mettrai son lien de téléchargement. (Depuis le site officiel de Microsoft)

L'idée m'était venue après un TD (en informatique 3ème année) sur Prolog. Langage singulier mais intéressant. On devait programmer les contraintes (pas 2 chiffres identiques en ligne, en colonne et dans les blocs 3x3), et Prolog résolvait la grille. Vu que les Sudoku me passionnaient, j'ai eu envie de programmer un logiciel qui faisait la même chose, mais en plus spécifique, donc plus performant. En Prolog on attend quelques secondes avant d'avoir la solution. J'ai été stupéfait de voir qu'avec un autre langage, la solution est immédiate, quelque soit la grille.
J'ai utilisé l'algorithme appelé "Back tracking". En gros on essaie toutes les possibilités sous forme d'arborescences, et quand la contrainte n'est pas respectée, on revient en arrière. D'où le nom de cet algorithme. C'est un algorithme récursif.

Pour générer les grilles. D'abord je générais une solution (parmi une infinité, avec des valeurs correctes choisies au hasard) qui partait d'une grille vide. On obtient une grille pleine et correcte bien-sûr.
Toujours en utilisant le back-tracking, mais qui donnait la profondeur dans l'arborescence de la valeur trouvée qui fonctionne. Ce qui exprime la difficulté de la trouver.
Une fois la grille pleine, j'enlevais au fur et à mesure une valeur d'une case au hasard et je résolvais la grille obtenue. Une bonne grille n'a qu'une seule solution. Donc si la nouvelle grille avait plus d'une solution, je remettais le chiffre dans la case et je recommençais. (j'éliminais le plus de cases possibles. Après les grilles valaient ce qu'elles valaient. Pas de belles symétries dans la grille présentée)
Selon le niveau de difficulté, je choisissais les valeurs les plus profondes dans l'arborescence.
Et pour nuancer les niveaux de difficultés, c'était seulement du paramétrage.
N'importe quelle grille initiale est résolue avant le jeu. (Mais évidemment pas affichée). C'est pour l'éventualité où le joueur utilise les aides.


La résolution d'une grille est instantanée, mais la création d'une grille peut prendre une dizaine de secondes pour le niveau "Très difficile"

Vous pouvez sauvegarder votre partie (pour la continuer plus tard, avec son historique, tous les coups sont stockés, on peut naviguer entre les coups, soit revenir en arrière ou aller vers l'avant), être aidé (genre éviter les étourderies ou carrément n'accepter que la bonne solution d'une case), vous pouvez aussi saisir une grille existante.

Voilà.

Enjoy !



[EDIT]
D'abord générez une grille aléatoire au niveau voulu, ou saisissez une grille existante.
Pour jouer il suffit de cliquer sur une case et d' entrer le chiffre.
Il y a deux modes de saisie. Quand la sélection est bleue, vous entrez la valeur définitive (enfin vous pouvez quand-même l'écraser plus tard, si vous vous êtes trompé). Quand la sélection est verte, vous entrez des possibilités. (Les petits chiffres dans la case)
Pour passer d'un mode à l'autre, il suffit d'appuyer sur la touche Shift.

C'est un programme que j'avais fait pour moi, sans l'intention de le publier nulle part. Ne cherchez pas à résoudre une grille vide, il va chercher à trouver toutes les grilles pleines possibles !!!
Vous seriez mort avant qu'il ait fini. . On peut dire que le programme bloque. Il ne répondra plus, il faudra le fermer de force.
Et ne vous attendez pas à des acclamations quand vous terminez une grille, il ne se passera rien.

[freeshost]

J'aime bien le niveau infernal.

Bon, la rapidité n'est pas mon critère.

[Bubu]

Bon.
Je vois que ce sujet déchaîne les foules.
Calmez-vous s'il vous plait car vous allez faire exploser le serveur.
Surtout, cachez votre joie et ne sombrez pas dans l'hystérie collective.

[Zia .]

J'aurais pas d'info super captivantes à apporter ici, mais j'ai une petite addiction au sudoku.
J'ai toujours un carnet que j'emporte partout (sauf au boulot, au risque de négliger mon travail), et il y a des périodes où je ne fais vraiment que ça de mon temps libre.
C'est vraiment super relaxant et je conseille l'usage du sudoku à tous les gens stressés que je croise. J'ai du mal à comprendre comment on peut ne pas se sentir bien en faisant un sudoku
Par contre je suis encore loin du niveau infernal

[Lilas]

Rien à dire sur le sudoku en particulier mais bravo et merci pour la description de l'algorithme. Je m'y essaierai peut-être en VBA si j'ai à nouveau l'occasion de m'ennuyer ferme au travail.

[Bubu]

Rien à dire sur le sudoku en particulier mais bravo et merci pour la description de l'algorithme. Je m'y essaierai peut-être en VBA si j'ai à nouveau l'occasion de m'ennuyer ferme au travail.

Hellow.

Sur wikipedia en anglais on a le pseudo-code et justement l'exemple de résolution du sudoku.
https://en.wikipedia.org/wiki/Backtracking
La version française de l'article n'est qu'une ébauche. C'est pourquoi je mets le lien vers la version anglaise.

L'algorithme de résolution d'un sudoku est très simple, beaucoup plus que cela ne paraît sans doute.
Et l'algo retenu (le backtracking) ne résout pas la grille comme le ferait un humain. Un humain cherche par déduction à éliminer les possibilités pour chaque case, pour finir par une seule valeur possible.
(Enfin, il y des grilles, les plus difficiles, où on est obligé de choisir une possibilité parmi plusieurs candidates sans savoir laquelle est la bonne, et de continuer la résolution. Si ce n'était pas la bonne, il faut effacer tout ce que l'on a fait depuis et tenter une autre possibilité. (Personnellement, je trouve que ça casse l'intérêt du jeu, car c'est un choix d'une possibilité parmi d'autres au hasard. D'accord je suis mauvais perdant !
J'en parle surtout car c'est la façon de faire des algorithmes utilisés pour ordinateurs. Et cela fait des merveilles. (exécuté par un ordinateur)

Je décris plus en détail l'implémentation de l'algorithme de résolution d'une grille :

En préambule (cela ne constitue pas le cœur du sujet, mais ça aide.) :

D'abord il faut faire une interface utilisateur graphique (une grille de 9x9 cases) avec son système de sélection de cellule, et l'entrée d'une valeur dans la cellule sélectionnée. (L'idéal est de faire en plus un système de saisie de grille existante.)
C'est surtout pour voir ce que l'on fait et vérifier que l'algorithme est bien implémenté.

Commençons :
Ensuite il faut faire trois méthodes qui vérifient les contraintes. A savoir :

• Pas 2 chiffres identiques dans une ligne

• Pas 2 chiffres identiques dans une colonne

• Pas 2 chiffres identiques dans un bloc 3x3

Après on les utilisent toujours ensembles, encapsulées dans une unique méthode.

Ensuite il faut une méthode qui vérifie qu'il reste bien au moins une case vide. Soit que la grille n'est pas pleine.

Enfin, on est paré au combat! L'algo de recherche des solutions. (Car il peut parfois y avoir plusieurs solutions à une grille. En général, c'est mal vu, mais c'est possible, donc ... )

Dans une méthode qui peut s'appeler elle-même, (soit en récursivité) :
On énumère toutes les possibilités (chiffres de 1 à 9) pour chaque case vide (valeur zéro) (2 boucles imbriquées qui balaient toute la grille) . Pour chaque possibilité, on vérifie que les contraintes sont respectées. Ensuite on relance la méthode récursive sur les nouvelles valeurs vides qui restent au niveau de la profondeur actuelle pour générer des possibilités à la profondeur suivante.).( La fonction récursive s'appelle donc elle-même). et ainsi de suite... Rebelote comme dirait l'autre. (Par contre ne me demandez pas qui est l'autre : nul ne le sait)
On arrête la récursivité dans 2 cas : (soient 2 conditions d'arrêt)

• Soit les contraintes ne sont pas respectées. Dans ce cas on abandonne direct. On ne se préoccupe plus de cette partie de l'arborescence.

• Soit quand les contraintes sont respectées et que la grille obtenue est pleine. Dans ce cas la résolution est terminée, on peut stocker la grille résultat comme une des solutions

L'algo s'arrête de lui-même une fois que toutes les grilles correctes de l'arborescence sont pleines (et qu'il a expulsé toutes les mauvaises grilles, celles qui ne respectaient pas les contraintes, 99% des grilles intermédiaires générées ! ), et constituent donc l'ensemble des solutions.

Bon courage !

Le backtracking, c'est du bovinage (on essaie toutes les possibilités sans chercher à comprendre), mais en stockant les possibilités sous forme d'une arborescence, ce qui change tout. Heureusement, car sinon en force brute de bovin, il faudrait l'éternité pour résoudre une grille. Donc le backtracking, c'est la solution de bovins gentlemen. Mais tant que ça marche ...

Après c'est un algorithme utilisé partout pour les AI des jeux de logique combinatoire : les échecs, le puissance4, le morpion (ouais bof... ), les tours de Hanoï, etc.

Enfin pour les jeux à 2 joueurs, c'est une variante qui est utilisée : le Negamax. C'est une variante, qui utilise le même principe. Une arborescence qui stocke la partie.
Pour remplir l'arborescence, on choisit, tour après tour, la meilleure réponse du joueur, et après la meilleure réponse de Skynet. Et on enchaine comme cela, selon un niveau de profondeur maximale d'analyse de l'arborescence.

J'ai perdu le code, mais j'avais fait une AI de puissance 4 qui analysait 9 coups à l'avance (coups de l'AI + coups du joueur compris). Mal programmée, il fallait plusieurs minutes avant d'avoir son coup. Lente peut-être, mais redoutable !

C'est parce que le temps de recherche de solution est exponentiel en fonction de la profondeur maximale choisie.

[Bubu]

Ce sujet m'a donné envie de m'y remettre !
J'ai réussis 2 fois le niveau "Très difficile".
Mais sinon j'échoue à chaque fois.
Soit je suis bloqué, soit j'ai fait une étourderie.

Si vous voulez des grilles très difficiles, demandez-moi, je posterai des grilles issues d'impression-écran.
Les grilles générées semblent simples au début. Mais c'est une chimère !!!
Même si vous avez résolu la moitié de la grille, la difficulté montre le bout de son nez !!!

Enfin le plus simple, c'est de télécharger l'appli. D'accord, c'est une appli Windows.

[freeshost]

Va donc ! Donne-nous des grilles pour griller nos neurones !

[Bubu]

Voici 4 grilles générées en mode "très difficile" par l'appli, je ne les ai pas essayé.
(Je tiens à préciser que les grilles que je propose n'ont qu'une seule solution, une grille qui a plus d'une solution est considérée comme faible, non aboutie ).
Galère l'impression écran avec PSP 7....

Image18.png

Image16.png

Image7.png

Image5.png

Prenez vous la tête avec passion!

Amusez-vous bien quand même !

Si vous le désirez plus tard, j'en posterai d'autres.

[freeshost]

Bon, de quoi s'amuser ce soir.

[Bubu]

Désolé de remettre ce sujet en haut de la pile, mais...

Bon, de quoi s'amuser ce soir.

J'aimerais beaucoup avoir ton retour sur ces 4 grilles...
As-tu réussi à les résoudre, voire carrément les as-tu trouvé faciles ?

Car je peux travailler sur les paramétrages de difficultés, si elles sont trop simples.
(Comme mettre moins de valeurs dans la grille initiale, et être encore plus dur sur la profondeur dans l'arborescence des valeurs à trouver)
Dans les messages précédents, basés sur des ordis qui ont 10 ans aujourd'hui, oui, cela arrivait qu'il faille une dizaine de secondes pour générer des grilles en mode très difficile.
Maintenant, bof. Non. 2 3 secondes suffisent. Donc je peux augmenter la difficulté à nouveau.

Une bouteille à la mer...


[EDIT]
J'envisage de plus en plus de porter cette appli sur Android. (En gros tout refaire en java. Mais avec des graphismes vachement plus mieux! )
(Evidemment, gratuite, pas d'achats via l'application, ni d'annonces publicitaires).
Juste pour le plaisir.

Ça vous intéresserait ?

[freeshost]

Bon, les deux premières m'ont pris respectivement 17 min + 35 s et 26 min + 40 s. Après les raisonnements simples, j'ai à chaque fois testé une hypothèse.

En faisant la troisième, je croyais qu'elle allait être simple, pouvant bien la remplir seulement avec des raisonnements simples. Puis... j'aboutis à une impossibilité, je recommence, rebelote... puis je vérifie la grille de départ... que j'avais mal copiée.

Bon, je fais une pause.

[Bubu]

Bon, les deux premières m'ont pris respectivement 17 min + 35 s et 26 min + 40 s. Après les raisonnements simples, j'ai à chaque fois testé une hypothèse.

En faisant la troisième, je croyais qu'elle allait être simple, pouvant bien la remplir seulement avec des raisonnements simples. Puis... j'aboutis à une impossibilité, je recommence, rebelote... puis je vérifie la grille de départ... que j'avais mal copiée.

Bon, je fais une pause.

Merci pour ton retour très fructueux.
Pourquoi tu te chronomètres, vu que tu dis que le temps de résolution t'est indifférent ?
Moi aussi, j'aime prendre mon temps. Qu'importe 1/2 heure ou une heure peu importe.
Merci encore.

Tu veux que j'en poste d'autres ? (Si tu as une imprimante, imprime-les pas de risque de mauvaise copie)

[freeshost]

D'habitude, je ne chronomètre pas. J'ai chronométré juste parce que tu m'as dit que tu voulais un retour.

Tu pourrais faire un pdf avec des grilles des plus difficiles. Je le téléchargerai plus tard.