RÉSOLUTION ET CRÉATIONS DE SUDOKUS

Messages postés
244
Date d'inscription
vendredi 6 mai 2005
Statut
Membre
Dernière intervention
6 avril 2008
- - Dernière réponse : 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
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/34778-resolution-et-creations-de-sudokus

le_duche
Messages postés
159
Date d'inscription
lundi 13 juin 2005
Statut
Membre
Dernière intervention
26 février 2009
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
"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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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 -
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
-
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
-
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 -
Vraiment pas mal du tout...

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

Good programmation à tous