RÉSOLUTION ET CRÉATIONS DE SUDOKUS

Signaler
Messages postés
244
Date d'inscription
vendredi 6 mai 2005
Statut
Membre
Dernière intervention
6 avril 2008
-
Messages postés
159
Date d'inscription
lundi 13 juin 2005
Statut
Membre
Dernière intervention
26 février 2009
-
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

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...
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 ;)
Messages postés
159
Date d'inscription
lundi 13 juin 2005
Statut
Membre
Dernière intervention
26 février 2009

Ben fais le alors ^^
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 :(
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...
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...
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
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.
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...)
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...
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é).
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é.
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 !
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é
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
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é
Messages postés
159
Date d'inscription
lundi 13 juin 2005
Statut
Membre
Dernière intervention
26 février 2009

Voilà ! c'est fait...
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...
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?
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...
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
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...
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 !
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...
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
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... ^-^
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
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.
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
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 !
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.
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... ^_^)
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