RÉSOLUTION ET CRÉATIONS DE SUDOKUS

Commentaire de le_duche le 25/11/2005 10:32:41

C'est clair qu'il y avait interet à le commenter celui-là !
Surtout que j'avais la flemme de surdéfinir l'opérateur [] afin d'avoir une forme matricielle...
je pourrais le faire dans les améliorations...
Mais pour l'instant je vais plutot me pencher sur le problème de générer des Sudoku aléatoirs avec une seule solution possible.
(j'ai dejà ma petite idée... ^_^)

Commentaire de ncoder le 25/11/2005 19:09:55

Bonne idée LE_DUCHE de générer des Sudokus aléatoires !

Commentaire de Kirua le 25/11/2005 22:26:07

Bonjour, je trouve que c'est une excellente idée de faire un compromis entre "réflexion humaine" et récursion propre au pouvoir des ordinateurs. Je pense que tu peux en tirer un simple algorithme de "rating" des sudoku, donner leur niveau. Par exemple, tu peux attribuer un point de difficulté par case trouvée par la "position unique", et x² ou même x³ points pour une case trouvée en faisant x hypothèses, puisque c'est bcp plus dur de faire plusieurs hypothèses de suite sans s'y perdre.

Commentaire de le_duche le 26/11/2005 20:46:39

Désolé, j'avais un peu la tête dans le *** quand j'ai écrit mon post ci-dessus, et il n'est pas très clair... ^-^

Commentaire de le_duche le 28/11/2005 14:30:08

si tu es sous linux, enlève le system("pause"); c'est une commande dos.
Si tu n'est pas sous linux, essaye en replacant cette ligne par:

int schtroumpf;
cin >> schtroumpf;

si ca ne marche toujours pas, je ne sais pas...

Commentaire de le_duche le 29/11/2005 17:42:44

pas besion de me vouvoyer ^-^ je n'ai que 20 ans...

Commentaire de le_duche le 05/01/2006 22:08:46

Il faut faire un projet, avec un fichier main et une fonction main dedans... ici ce n'est qu'un librairie, tout comme iostream par exemple...

Commentaire de le_duche le 16/01/2006 11:34:16

ok j'en ferai un ce soir et je le posterai demain...
Mais par exemple, tu crée un objet sudoku, tu le génère au niveau voulu, et tu le fais afficher. Si tu sais utiliser les fonctions de l'imprimante, tu lui fait imprimmer. Tu tente de le résoudre, puis tu lui fait afficher la solution...

Commentaire de yserver le 15/02/2006 18:27:53

J'ai pas lu ton code, mais à la lecture de la déscription : une petite proposition pour améliorer la rapiditer du code et eviter de nombreuses hypothèses.

Tu peux rechercher dans chaque zonne des doublettes (x,y) (triplettes...) de candidats et ainsi supprimer ces candidats (x et y) des candidats potentiels des autres cases de la zone.
En plus claire si dans une zone n cases ont pour candidats : (1,2,..,n) alors ces candidats seront obligatoirement dans ces n cases et ne sont donc plus des candidats potentiels des autres cases de la zone

Dans le même esprit, tu peux rechercher les chaines disjointes. C'est à dire si n (x,y,...) candidats sont présents dans n cases, sans necessairement être présents dans dans chacunes des n cases. Alors c'est n candidats finiront donc forcéments dans ces n cases et ne sont plus des candidat potentiels pour les autres cases de la zone.
Pour être plus claire et avec 3 candidats. Supposons 3 cases :
x avec pour candidats (1, 5)
y avec pour candidats (1, 8)
z avec pour candidats (5, 8) ou z (1, 8) ou z(1, 5, 8)
Alors le groupe de candidats (1,5,8) sera forcement dans les case x, y et z et nul part ailleurs.

Juste une suggestion car je me suis beaucoup amusé à coder ça (ca fait des boucle...).

Bonne soiré

Commentaire de yserver le 16/02/2006 17:18:30

Je suis pas d'accord, pour plusieurs raison.
1- tu semble t'être arreté au doublette mais avec 3 4 .. ca marche et alors ton raisonnement semble ne pas prendre en compte toutes les données.
2- tu ne parle pas des chaines disjointes
2- en implementant en plus dans mon programme cette recherche de doublette triplette et chaine disjointe, je resolvais certain sudoku sans hypothese alors que avant ces fonctions non.
3- si j'ai ajouté toutes ces fonctions supplementaires c'est pour pouvoir résoudre des sudoku que si non je ne resolvais que par l'utilisation d'hypothèse que mon prog ne fait pas et que les résultats étaient probant.
4- un contre exemple cette adresse http://www.mots-croises.ch/Sudoku/grille.htm?t=N4 en sans la recherche des doublettes/tiplettes mon programme ne le resoud pas et avec si.

Cela dit c'est pas forcement plus performant de traiter tous c'est cas de figure le test est peut etre plus rapide. Mais je pense que la recherche de c'est deux type de figure doit grandement améliorer les performances (c'est de la pure intuition.)

Bonne soiré

Commentaire de yserver le 16/02/2006 19:47:31

SI tu est interessé je peux t'envoyer un bout de mon code en vba avec excel.
J'ai fait ca fissa pour des collegues qui me gonflaient avec leur sudoku. Je dis ca car moi ca ne m'amuse pas bcp mais je me suis bcp amuser en faisant ce petit prog. En plus j'ai découvert ainsi un monde passionnant celui du sudoku.

bonne soiré.

Commentaire de le_duche le 17/02/2006 13:36:20

Ben en fait j'ai fait une fonction qui résoud les grilles, et chaque fois qu'il doit faire une supposition, il choisit une valeur aléatoire parmis les chiffres encore possibles.
Donc en lui donnant une grille vide, il me génère une grille de Sudoku aléatoire...

Commentaire de Kirua le 17/02/2006 22:53:18

Je connais bien le printemps des sciences, j'y étais allé voir pas mal de choses, entre autre une présentation sur les algos génétiques faite par (entre autres) un coder de cppfrance aussi :).

C'est en mars toujours? Je tenterai d'y aller, c'est tjs sympa :) Et pourquoi pas avec quelqu'un que tu connais bien, comme la fois passée.

Commentaire de Eagle4 le 03/04/2006 17:30:14

dis moi tu crois qu'il serait possible de générer les grilles aléatoires avec toutjours le meme niveau de difficulté ??? genre que chaque case vide en normal propose 2 ou 3 possibilité de chiffre environ (je dis environ car y a forcement une case à une solution ^^ sinon le sudoku n'aura pas qu'une solution...) mais c'est histoire d'homogénisé les générations...

Commentaire de Eagle4 le 05/04/2006 20:20:39

arf c'est c** ca, j'arrive pas à trouver un bon générateur qui fais ca :(

Commentaire de Eagle4 le 05/04/2006 20:28:56

oui mais là je dois bien avouer que ce niveau est trop élevé pour moi lol... nan sérieusement, c'était surtout pas pour te vexer, il est super bien foutu ton code ;) d'ailleur c'est parce que ton code est super bien fais que je te demandais à toi ^^
m'enfin bon je vais essayé de me débrouiller merci quand meme ;)