Commentaires sur une source : RÉSOLUTION ET CRÉATIONS DE SUDOKUS

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
6 avril 2006 à 13:56

Ce que tu peux toujours faire, c'est ajouter des critères de création dans le test, mais comme ma construction est aléatoire, il est possible que l'algo mette alors beaucoup de temps pour créer une grille valide...

cs_Eagle4 Messages postés 10 Date d'inscription jeudi 12 février 2004 Statut Membre Dernière intervention 5 avril 2006
5 avril 2006 à 20:28

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 ;)

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
5 avril 2006 à 20:24

Ben fais le alors ^^

cs_Eagle4 Messages postés 10 Date d'inscription jeudi 12 février 2004 Statut Membre Dernière intervention 5 avril 2006
5 avril 2006 à 20:20

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

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
5 avril 2006 à 20:05

Pas avec ma méthode aléatoire en tous cas...

cs_Eagle4 Messages postés 10 Date d'inscription jeudi 12 février 2004 Statut Membre Dernière intervention 5 avril 2006
3 avril 2006 à 17:30

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...

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
18 févr. 2006 à 13:13

Ok ben à bientot alors :D

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
17 févr. 2006 à 22:53

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.

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
17 févr. 2006 à 13:42

note pour Kirua: Tu sais peut-etre de quoi il s'agit, je présente le Sudoku (mon programme de résolution) au printemps des Sciences organisé par l'ULB, dont le thème est le cerveau (on bosse sur les juex de logique...)

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
17 févr. 2006 à 13:36

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...

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
17 févr. 2006 à 12:41

"J'ai étudié les math qui sont derrières", le contraire m'aurait étonné :). Mais tu as approfondis les maths de la résolution ou de la construction des grilles? De ce que j'ai pu voir sur les forums spécialisés, point de vue niveau d'abstraction, c'est franchement pas pareil :/ Bcp plus simple de résoudre que de créer (avec toute la rigueur associée; juste générer des grilles "qui marchent" c'est pas compliqué).

yserver Messages postés 203 Date d'inscription lundi 2 août 2004 Statut Membre Dernière intervention 8 septembre 2006
16 févr. 2006 à 19:47

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é.

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
16 févr. 2006 à 17:26

Je testerai ce sudoku sur mon programme (sais pas le faire ici), mais j'vais testé les Sudoku du Figaro et d'un journal Belge, et à chaque fois, il trouvais sans supposition.
Mais si ta grille me le fait faire avec une supposition, ca m'interesse meme beaucoup, pcq je ne sais donc pas si cette partie de mon code a un bug :p

++ Bonne Prog !

yserver Messages postés 203 Date d'inscription lundi 2 août 2004 Statut Membre Dernière intervention 8 septembre 2006
16 févr. 2006 à 17:18

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é

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
16 févr. 2006 à 14:36

J'ai étudié les math qui sont derrières, et ce que tu me propose est doffice trouvé par mes deux procédures sans devoir faire de supposition (à condition que le sudoku de départ contienne une seule solution) Cela vient du fait que si tu as un doublet quelque part, alors les autres cases qui ne sont pas dans le doublet seront forcément déterminées univoquement par le reste du tableau. D'autre part, comme le tableau ne doit posséder qu'une seule solution, trouver se doublet se fera indépendemment de ce qui reste dans la colonne, donc on y arrivera aussi...

++ merci du conseil q-meme :D

yserver Messages postés 203 Date d'inscription lundi 2 août 2004 Statut Membre Dernière intervention 8 septembre 2006
15 févr. 2006 à 18:27

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é

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
19 janv. 2006 à 10:59

Voilà ! c'est fait...

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
16 janv. 2006 à 11:34

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...

lamarch Messages postés 3 Date d'inscription dimanche 15 janvier 2006 Statut Membre Dernière intervention 11 décembre 2009
16 janv. 2006 à 02:06

Ce n'est pas évident de savoir quoi mettre dans le main...

Si t'en as fait un , est ce que tu pourrais le mettre en téléchargement stp?

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
5 janv. 2006 à 22:08

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...

Fflaite Messages postés 1 Date d'inscription lundi 2 janvier 2006 Statut Membre Dernière intervention 2 janvier 2006
2 janv. 2006 à 18:18

salut à tous!
j'ai télécharger ce programme qui ma foie et fort remarquable !!
seulement lorsque je le compile avec dev c++, le programme ne se lance pas et il est affiché :
[Linker error] undefined reference to `WinMain@16'
ld returned 1 exit status
Que dois je configurer dans dev afin de lancer le programme ?
merci
Fflaite

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
29 nov. 2005 à 17:42

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

cs_dautrey Messages postés 6 Date d'inscription mardi 9 novembre 2004 Statut Membre Dernière intervention 29 novembre 2005
29 nov. 2005 à 04:51

Merci, ça marche, je suis sous windows xp ... j'ai rien compris.
Votre code est remarquable.
Bravo pour votre site. Très didactique !

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
28 nov. 2005 à 14:30

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...

cs_dautrey Messages postés 6 Date d'inscription mardi 9 novembre 2004 Statut Membre Dernière intervention 29 novembre 2005
28 nov. 2005 à 08:57

Avec quel compilateur avez-vous compilé le cpp ?
quand j'essaye de compiler
Le mien c'est Bloodshed DEV-C++ Version 4
il est pas très polis !
il me balance les deux erreurs suivantes:
sudoku.cpp: In function `int main(int, char **)':
sudoku.cpp:416: implicit declaration of function `int system(...)'
Quel réglage je dois apporter pour que ça marche ?
Cordialement.
François DAUTREY

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
26 nov. 2005 à 20:46

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... ^-^

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
26 nov. 2005 à 13:39

supers03, je crois que je vais reprendre ton idée pour généré un sudoku aléatoire!
J'ai déjà fait la fonction pour générée une grille complète, mais il me reste à déterminer les case que l'on offre au joueur comme indices.
J'ai essayé hier soir une méthode qui ne marche pas du tout:
while(j'ai plus d'une solution)
{
ajouter une case au hasard en plus comme information
}

Et parfois il ne me reste que 5 ou 6 cases libres apres...

J'ai donc encore un peu de boulot la dessus :D

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
25 nov. 2005 à 22:26

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.

juju_browser Messages postés 8 Date d'inscription lundi 23 février 2004 Statut Membre Dernière intervention 25 novembre 2005
25 nov. 2005 à 20:36

ton site est vraiment bien
http://leduche.blog.jeuxvideo.com/
chapo!

tebrowser

ncoder Messages postés 244 Date d'inscription vendredi 6 mai 2005 Statut Membre Dernière intervention 6 avril 2008 1
25 nov. 2005 à 19:09

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

supers03 Messages postés 106 Date d'inscription mardi 6 janvier 2004 Statut Membre Dernière intervention 1 décembre 2008
25 nov. 2005 à 18:25

Salut Le_Duche
J'ai fait un programme similaire la semaine dernière. en fait pour créer la grille j'en construit une aléatoirement, puis je supprime une à une les cases et à chaque fois j'essai de re_remplir la grille. Ainsi je suis sur que ma grille finale est faisable sans devoir mettre des valeurs au pif en plein milieu (chose que je trouve completement bete dans un jeu de reflexion). Je suis conscient de la lourdeur de cette méthode mais de toute façon ça va tellement vite (moins d'une seconde) que ça ne dérange pas.

le_duche Messages postés 159 Date d'inscription lundi 13 juin 2005 Statut Membre Dernière intervention 26 février 2009
25 nov. 2005 à 10:32

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... ^_^)

ncoder Messages postés 244 Date d'inscription vendredi 6 mai 2005 Statut Membre Dernière intervention 6 avril 2008 1
24 nov. 2005 à 19:41

Vraiment pas mal du tout...

Programme bien réfléchi mais meme avec les commentaires il faut s'accrocher !

Good programmation à tous

RÉSOLUTION ET CRÉATIONS DE SUDOKUS

Votre réponse

Discussions similaires