Salut !

Vous connaissez le jeu du Sudoku, ce jeu de chiffres a la mode en ce moment, ou vous devez remplir la grille (un peu comme un carré magique)

Je vous propose un algo pour les résoudre : vous remplissez le fichier test.txt en mettant des . quand la case est vide (voir l´exemple), lancez le programme, celui ci remplit les cases manquantes ! (fichier out.txt comme résultat)

http://perso.numericable.fr/~fvirtman/sudoku.zip

J´ai mis la source avec ! par contre, j´ai fait aucune interface graphique (pas eu le temps)

PS : je ne suis pas venu depuis tres longtemps, je ne peux plus venir du tout en ce moment hélas. Mais je reste dispo par mail, et j´update mon tuto de temps en temps (prochainement un petit tuto pour faire du texte coloré sans conio...)

Ca marche comment?
Ca teste toutes les possibilités jusqu´à trouver la bonne?

Tout a fait.
ça cherche une case vide. S´il n´y en a pas, alors c´est que c´est complet, tu as gagné.
Si une case est vide, ça regarde, parmi les 9 chiffres, lesquels sont possible de mettre (avec les regles du sudoku)
Puis, pour chaque cas, ça recommence.
L´algo n´est pas si long car en général, pour chaque case, tu as 2 ou 3 possibilités a tout casser. De plus, plus tu avances, moins tu as de possibilités pour une case, donc la recursivité se casse tres vite, ce qui permet a l´algo d´etre rapide.
Cependant, comme la récursivité était tres profonde, j´ai préféré la casser et la remplacer par un algo itératif avec une gestion manuelle de pile (le std::stack) : plus de risque de "stack overflow"

J´imagine que si la fonction avait été récursive ca aurait planté en cas de grille impossible non ?

Non, ça n´aurait pas planté a cause d´une grille impossible : quoiqu´il arrive, il s´arrete a un moment.

ça plantait, si je mettais en mode debug (sans parametres d´extention /Zm qui augmente le tas) : au bout de 80 récursions car il empilait des structures "Sud" et les parametres de debuggage.
Mais cela dans tous les cas : car meme quand la grille est possible, il faut quand meme descendre tout en bas de l´arbre de récursion.
L´astuce de transformer un algo récursif en itératif peut sauver la vie dans ce genre de cas

t´as jetté un oeil sur ma source ?
Je me suis amusé à faire un petit test:
Je lui ai demandé d´afficher lorsqu´il entrait en récursivité, et il se trouve que tous les Sudoku que l´on trouve dans les journaux (meme en mode difficile) ne rentre jamais dans le récursif et sont directement résolu par les deux procédures avant...
A croire que c´est un critère des générateurs de grilles à solution unique...
J´en viens à me demander si toute grille à solution unique peut etre résolu par mon algo sans la récursivité...

oups j´ai pas donné ma source...

http://www.cppfrance.com/code.aspx?ID=34778

(et j´ai loupé mon smiley )

Je ne penses pas,
j´ai lu sur wikipedia que le probleme etait NP-Complet (je n´ai pas lu la preuve qui etait fournie); ce qui semble dire qu´il ´existe pas d´algorithme polynomial (ou alors tu as gagné un million de dollards) pour résoudre ce probleme de facon, et l´algorithme présenté est polynomial.
ca doit tout simplement vouloir dire que ce qui est donné dans les journaux sont des instances particulierement simple du problème

Moi si j´étais dans un journal a devoir créer des sudoku tous les jours, ce serait simple :
Mon programme actuel - et peut etre le tien aussi - s´arrete quand il trouve une solution.
Il suffirait d´une modif : quand il trouve une solution, il la push dans une liste, et il continue.
et a ce moment la, il trouverait toutes les solutions a partir du fichier d´entrée.
Il suffit alors de mettre le fichier d´entrée a "que des cases vides"
et tu lances le prog : tu obtiens la liste de TOUS LES SUDOKU POSSIBLES...

Et puis hop ! tous les jours, payé pour en choisir un au random
Ah le beau métier !

j´ai pas regardé ton prog car je n´ai pas de loggin sur ton site tu ne veux pas le mettre sur rafb.net ?
PS : je pars en WE, donc je risque de ne pas répondre tout de suite...

une légère adaptation de ton programme, et il pourrait effectuer lui-même le choix pseudo-aléatoire de la grille, puis l´e-mailler à la rédaction du journal.
Tu peux aussi t´arranger pour qu´il check en ligne le versement de ta paye une fois par mois, calcule tes impots une fois par an et renégocie tes credits avec ta banque tous les 5 ans.
Et pendant ce temps tu bois des margaritas aux bahamas !

ya pas moyen de faire autrement qu´en brute force? parce que la ca fait quand meme du 9^(nb_de_cases_vides)

je suis sur qu´avec un réseau de neurones c´est possible ce machin la :D

voilà je génère aléatoirement en moins d´un dixième de seconde...
J´ai presque terminé la génération avec les indices pour le joueur...

fracart, non il n´y a pas autre chose qu´un brute force.
un reseaux de neuronnes est une technique probabiliste qui ne donne donc pas a coup sur le bon resultat.

apres, de bonnes heuristiques pour ce probleme peuvent exister... c´est un autre probleme.

oui, mais les sudoku avec 9 cases c´est dépassé... Maintenant il faut le faire avec 16 cases (carrés de 4*4 donc) là il y a du challenge (et puis les programmes vont tourner plus longtemps donc il faudra demander une augmentation de salaires pour les générer).

pas bete ca!
on pourrait meme essayer de généraliser avec n²xn² cases par grilles... avec n au choix de l´utilisateur...