Projet d'été sur SUDOKU!! Aidez-nous s'il vous plait...

Question

Au préalable, nous tenons à remercier tous ceux qui contribuerons à notre projet...

On nous demande d'écrire un programme C qui permet de Générer des Grilles Aléatoires de SUDOKU. Nous avons parcouru la plupart des sujets et codes sources proposés sur le site mais la plupart fait intervenir la notion d'objet (chose que nous allons étudier l'année prochaine).

Bref, nous voulons juste connaître l'algorithme du génerateur de grilles, nous avons déja pensé à un algorithme qui part d'une grille vide et qui la rempli en choisissant des cases aléatoirement en utilisant des listes doublement chainées afin d'effectuer le backtracking en cas de contradiction...une fois la grille générée complètement on ne dévoile qu'un certain nombre des cases pour obtenir la grille du jeu...

Connaitriez-vous un autre algorithme qui soit plus performant??? nous avons discuté la possibilité de partir d'une grille de jeu déjà connue et d'effectuer une suite de permutations (lignes;colonnes,blocs) mais apparament ce n'est pas considéré comme une nouvelle grille (le site fr.wikipedia.org/wiki/sudoku précise que deux solutions sont différentes si et seulement si elles ne sont pas obtenues par les opérations sitées ci-dessus)

Merci de nous répondre...

gamemonde · Answer

vous avez pas chercher fort j'ai ecrit sudoku sur ce site en demandant des sources et pow directement le premier etais un sudoku avec des tableau non des objects 

http://www.cppfrance.com/codes/CREATION-SUDOKU-DIFFERENTS-NIVEAUX-RESOLUTION_34700.aspx

On nous demande d'écrire un programme C 
il a encore des ecoles qui travailles avec le c moi c'est directement le c++ et en 2er session ou trimestre c'est la notion d'object

perig · Answer

Salut,

Juste pour info (on sait jamais), j'ai un ami qui a codé un algorithme de résolution de Sudoku mais je crois me souvenir qu'il a pas utilisé le C
(C'est basé sur les méthode par contrainte mais j'en ai pas retenu plus lol, je peux lui demander plus d’info si ca intéresse qqn)

Bon courage pour votre projet

---Perig--- 
Pour vous servir 
Et parfois en galère 
Souvent même

Naruttibayo · Answer

Oui Perig ça nous interesse (merci à l'avance...)
Le sujet que gamemonde a mentionné n'est pas valide car il génère la même grille (les opérations de permutation de lignes colonnes... sont considérées comme une seule grille) et STP arrête de faire ton interessant et de faire des remarques désobligeantes... on a bien étudié la notion objet mais c'est juste que le travail demandé est en C...

CG85 · Answer

@ gamemonde : Je ne sais pas vraiment ce que tu reproches au langage C mais on en aura toujours besoin pour des raisons de symplicités (Utilisation du C comme langage intermédiaire pour des langages de hauts niveaux -Eiffel entre autre -) mais aussi par ce qu'il est l'ancêtre directe d'autres langages tel que ton cher C++ ....

gamemonde · Answer

non non ne vous en faites pas je rapproche rien au c c'est juste que j'ai ete surpris d;apprendre qu'il avais encore des ecoles qui passais par ce language c'est tout voyons quand j'apprenais tout seul la prog j'ai passer par le c avant d'allez au c++ mais mon ecole denie completement le c (au quebec) je vais me calmer lol vous aurrez plus de remarque s désobligeantes foi de programmeur. lol allons la vie est belle il faut en profite

salut a+

perig · Answer

Salut, desolé du temps de réponse : 
J'ai demandé a mon ami et voila ce qu'il ma répondu (moi j'y pige rien mais si ca vous parle...)

Enfait il faut installer GNU-Prolog c'est de la programmation logique par contrainte! (mais il a pas envie de me faire tout un cours dessus donc soit vous connaissez soit vous cherchez sur google :o)

Voici le source qu'il faut compiller aver gnu-prolog.

% Fonction d'affichage pour les sudokus classiques



affiche([]).
affiche([V,L,C,_|S]) :- 0 =:= C mod 9, 0 =:= L mod 3, write(V),nl ,nl, affiche(S).
affiche([V,_,C,_|S]) :- 0 =:= C mod 9, write(V), nl, affiche(S).
affiche([V,_,C,_|S]) :- 0 =:= C mod 3, write(V), write(' '), affiche(S).
affiche([V,_,_,_|S]) :- write(V), affiche(S).



% Fonctions permettant d'avoir les variables de la lignes numéro N.



ligne_bis([],_,R,R).
ligne_bis([V,N,_,_|S],N,M,R) :- ligne_bis(S,N,[V|M],R).
ligne_bis([_,_,_,_|S],N,M,R) :- ligne_bis(S,N,M,R).



ligne(G,N,R) :- ligne_bis(G,N,[],R).



% Fonctions mettant les contraintes de domaine sur les variables (dans le sudoku classique une variable va de 1 à 9)
% ainsi que les contraintes pour chaques lignes de la grille (tous les chiffres d'une lignes doivent être différents les uns des autres).



contraintes_lignes_bis(G,Vmax,Nmax,Nmax) :- ligne(G,Nmax,R), fd_all_different(R), fd_domain(R,1,Vmax).
contraintes_lignes_bis(G,Vmax,Ndeb,Nmax) :- ligne(G,Ndeb,R), fd_all_different(R), fd_domain(R,1,Vmax),
                                       Ndebplus is Ndeb+1, contraintes_lignes_bis(G,Vmax,Ndebplus,Nmax).



contraintes_lignes(G,Vmax,Nmax) :- contraintes_lignes_bis(G,Vmax,1,Nmax).



% Fonctions permettant d'avoir les variables de la Nième colonne.



colonne_bis([],_,R,R).
colonne_bis([V,_,N,_|S],N,M,R) :- colonne_bis(S,N,[V|M],R).
colonne_bis([_,_,_,_|S],N,M,R) :- colonne_bis(S,N,M,R).



colonne(G,N,R) :- colonne_bis(G,N,[],R).



% Fonctions mettant les contraintes pour chaque colonnes de la grille (aucun chiffre ne peut être identique dans une même colonne).



contraintes_colonnes_bis(G,Nmax,Nmax) :- colonne(G,Nmax,R), fd_all_different(R).
contraintes_colonnes_bis(G,Ndeb,Nmax) :- colonne(G,Ndeb,R), fd_all_different(R),
                                       Ndebplus is Ndeb+1, contraintes_colonnes_bis(G,Ndebplus,Nmax).



contraintes_colonnes(G,Nmax) :- contraintes_colonnes_bis(G,1,Nmax).



% Fonctions fournissant les variables du Nième bloque.



bloque_bis([],_,R,R).
bloque_bis([V,_,_,N|S],N,M,R) :- bloque_bis(S,N,[V|M],R).
bloque_bis([_,_,_,_|S],N,M,R) :- bloque_bis(S,N,M,R).



bloque(G,N,R) :- bloque_bis(G,N,[],R).



% Fonctions contraignant les variables à être toutes différente au sein d'un même bloque.



contraintes_bloques_bis(G,Nmax,Nmax) :- bloque(G,Nmax,R), fd_all_different(R).
contraintes_bloques_bis(G,Ndeb,Nmax) :- bloque(G,Ndeb,R), fd_all_different(R),
                                       Ndebplus is Ndeb+1, contraintes_bloques_bis(G,Ndebplus,Nmax).



contraintes_bloques(G,Nmax) :- contraintes_bloques_bis(G,1,Nmax).





% Fonction pour la résolution de sudoku (G: grille, Vmax: valeur maximum possible pour une variable, Lmax,Cmax,Bmax: nombre de lignes, colonnes et bloques).



sudoku(G,B,Vmax,Lmax,Cmax,Bmax) :- contraintes_lignes(G,Vmax,Lmax), contraintes_colonnes(G,Cmax), contraintes_bloques(G,Bmax), fd_labeling(G,[variable_method(ff),backtracks(B)]).



% Fonction pour la résolution de sudoku classique (grille 9x9 avec les variables pouvant aller de 1 à 9).



sudoku_classique(G,B) :- sudoku(G,B,9,9,9,9), nl, affiche(G).









Suivit d'exemple a exécuter apres la compilation du prog
% Exemples de problèmes de Sudoku classique
% avec comme niveau de difficulté facile - mmoyenne -difficile - diabolique.
% dans la structure d'entrée, chaque variable est suivie de 3 autres chiffres: la ligne, la colonne puis le bloque auquel elle appartient.



sudoku_classique(
[
_,1,1,1, _,1,2,1, _,1,3,1,  _,1,4,2, _,1,5,2, _,1,6,2,  _,1,7,3, _,1,8,3, 4,1,9,3,
8,2,1,1, 7,2,2,1, 3,2,3,1,  _,2,4,2, _,2,5,2, 6,2,6,2,  5,2,7,3, _,2,8,3, _,2,9,3,
_,3,1,1, _,3,2,1, 1,3,3,1,  _,3,4,2, _,3,5,2, 7,3,6,2,  3,3,7,3, 2,3,8,3, _,3,9,3,



9,4,1,4, _,4,2,4, _,4,3,4,  8,4,4,5, 1,4,5,5, 3,4,6,5,  _,4,7,6, _,4,8,6, _,4,9,6,
_,5,1,4, _,5,2,4, 8,5,3,4,  _,5,4,5, _,5,5,5, _,5,6,5,  1,5,7,6, _,5,8,6, _,5,9,6,
_,6,1,4, _,6,2,4, _,6,3,4,  4,6,4,5, 7,6,5,5, 2,6,6,5,  _,6,7,6, _,6,8,6, 5,6,9,6,



_,7,1,7, 8,7,2,7, 7,7,3,7,  1,7,4,8, _,7,5,8, _,7,6,8,  2,7,7,9, _,7,8,9, _,7,9,9,
_,8,1,7, _,8,2,7, 2,8,3,7,  9,8,4,8, _,8,5,8, _,8,6,8,  7,8,7,9, 4,8,8,9, 6,8,9,9,
6,9,1,7, _,9,2,7, _,9,3,7,  _,9,4,8, _,9,5,8, _,9,6,8,  _,9,7,9, _,9,8,9, _,9,9,9
],B).



sudoku_classique(
[
9,1,1,1, _,1,2,1, _,1,3,1,  6,1,4,2, 3,1,5,2, _,1,6,2,  _,1,7,3, _,1,8,3, 4,1,9,3,
_,2,1,1, 1,2,2,1, _,2,3,1,  2,2,4,2, 5,2,5,2, 8,2,6,2,  _,2,7,3, _,2,8,3, _,2,9,3,
_,3,1,1, _,3,2,1, _,3,3,1,  7,3,4,2, _,3,5,2, _,3,6,2,  _,3,7,3, _,3,8,3, 8,3,9,3,



6,4,1,4, 4,4,2,4, _,4,3,4,  _,4,4,5, 2,4,5,5, _,4,6,5,  5,4,7,6, _,4,8,6, _,4,9,6,
_,5,1,4, _,5,2,4, _,5,3,4,  _,5,4,5, _,5,5,5, _,5,6,5,  _,5,7,6, _,5,8,6, _,5,9,6,
8,6,1,4, 2,6,2,4, _,6,3,4,  5,6,4,5, _,6,5,5, _,6,6,5,  _,6,7,6, 9,6,8,6, _,6,9,6,



_,7,1,7, _,7,2,7, _,7,3,7,  _,7,4,8, _,7,5,8, _,7,6,8,  8,7,7,9, 7,7,8,9, _,7,9,9,
3,8,1,7, _,8,2,7, _,8,3,7,  _,8,4,8, _,8,5,8, 5,8,6,8,  _,8,7,9, 4,8,8,9, _,8,9,9,
_,9,1,7, _,9,2,7, 1,9,3,7,  _,9,4,8, 7,9,5,8, 6,9,6,8,  _,9,7,9, _,9,8,9, _,9,9,9
],B).



sudoku_classique(
[
_,1,1,1, _,1,2,1, _,1,3,1,  _,1,4,2, _,1,5,2, _,1,6,2,  _,1,7,3, _,1,8,3, 7,1,9,3,
_,2,1,1, _,2,2,1, _,2,3,1,  _,2,4,2, _,2,5,2, _,2,6,2,  6,2,7,3, 3,2,8,3, 4,2,9,3,
_,3,1,1, _,3,2,1, _,3,3,1,  9,3,4,2, 4,3,5,2, _,3,6,2,  _,3,7,3, 2,3,8,3, _,3,9,3,



5,4,1,4, _,4,2,4, 1,4,3,4,  7,4,4,5, _,4,5,5, _,4,6,5,  8,4,7,6, 6,4,8,6, _,4,9,6,
_,5,1,4, _,5,2,4, 9,5,3,4,  _,5,4,5, _,5,5,5, _,5,6,5,  _,5,7,6, _,5,8,6, 3,5,9,6,
_,6,1,4, _,6,2,4, _,6,3,4,  _,6,4,5, 8,6,5,5, _,6,6,5,  _,6,7,6, _,6,8,6, _,6,9,6,



4,7,1,7, 3,7,2,7, _,7,3,7,  5,7,4,8, _,7,5,8, _,7,6,8,  _,7,7,9, _,7,8,9, _,7,9,9,
_,8,1,7, 1,8,2,7, _,8,3,7,  _,8,4,8, 6,8,5,8, 8,8,6,8,  _,8,7,9, _,8,8,9, _,8,9,9,
_,9,1,7, _,9,2,7, _,9,3,7,  _,9,4,8, _,9,5,8, 3,9,6,8,  1,9,7,9, _,9,8,9, 9,9,9,9
],B).



sudoku_classique(
[
_,1,1,1, _,1,2,1, _,1,3,1,  _,1,4,2, 3,1,5,2, _,1,6,2,  _,1,7,3, _,1,8,3, _,1,9,3,
_,2,1,1, 1,2,2,1, 5,2,3,1,  _,2,4,2, _,2,5,2, _,2,6,2,  6,2,7,3, _,2,8,3, _,2,9,3,
6,3,1,1, _,3,2,1, _,3,3,1,  2,3,4,2, _,3,5,2, _,3,6,2,  3,3,7,3, 4,3,8,3, _,3,9,3,



_,4,1,4, _,4,2,4, _,4,3,4,  6,4,4,5, _,4,5,5, _,4,6,5,  _,4,7,6, 8,4,8,6, _,4,9,6,
_,5,1,4, 3,5,2,4, 9,5,3,4,  _,5,4,5, _,5,5,5, _,5,6,5,  5,5,7,6, _,5,8,6, _,5,9,6,
5,6,1,4, _,6,2,4, _,6,3,4,  _,6,4,5, _,6,5,5, _,6,6,5,  9,6,7,6, _,6,8,6, 2,6,9,6,



_,7,1,7, _,7,2,7, _,7,3,7,  _,7,4,8, _,7,5,8, _,7,6,8,  _,7,7,9, _,7,8,9, _,7,9,9,
_,8,1,7, _,8,2,7, _,8,3,7,  9,8,4,8, 7,8,5,8, _,8,6,8,  2,8,7,9, 5,8,8,9, _,8,9,9,
1,9,1,7, _,9,2,7, _,9,3,7,  _,9,4,8, 5,9,5,8, _,9,6,8,  _,9,7,9, 7,9,8,9, _,9,9,9
],B).


Ps : Lui il lui a fallu 2-3 semaines pour métriser la bete (ce projet c'est juste la prise en main avant son stage) Moi ca me fait penser a du code MathLab

---Perig--- 
Pour vous servir 
Et parfois en galère 
Souvent même

CG85 · Answer

Lu,


Bon Prolog c'est un langage de programmation logique basé sur un moteur d'inférence (je ne sais pas si c te parles mais en gros avec ce système tu donnes un problème ainsi que des contraintes et lui ce charge de trouver une solution).


Sérieusement, il suffit de prendre un peu de temps et de ne pas penser aux langages impératifs (C etc), de (re)lire le programme et au bout du compte tu comprendras ce qu'il à fait :)

+

perig · Answer

Ouai, j'ai compris en travers comment ca tournait mais vu que les Sudoku ca ne me passionne pas trop, j'ai pas cherché plus que ca. En plus les langages autre que C, C++ et php c'est pas trop mon truc :o) Mais c’est un minimum instructif et en rapport avec le sujet donc j’en fait profiter (ca démontre que pour certains problèmes d’autres langages peuvent êtres plus pratiques ;).

---Perig--- 
Pour vous servir 
Et parfois en galère 
Souvent même

7afousaa · Answer

mais le travail est demandé en c

Projet d'été sur SUDOKU!! Aidez-nous s'il vous plait...

9 réponses

Votre réponse

Discussions similaires