sudoku C++

Discussion dans 'Web, design' créé par leprincemiri, 27 Décembre 2007.

Statut de la discussion:
Fermée.
  1. Offline
    leprincemiri ex membre
    Hello tout le monde

    je suis en train de faire un sudoku en C++.

    J aimerais faire une fonction qui place des numéros de maniere aleatoire sur la grille, est ce que quelqu un pourrait me donner qq tuyaux ?

    merci d avance ;)
    leprincemiri, 27 Décembre 2007
    #1
  2. Offline
    the_quent1 Elite
    Bha un bete random non ?
    Tu réfléchi sur papier a comment les chiffres doivent etres (pas de doublons, ...) et tu te fais une petite fonction avec des conditions.
    the_quent1, 27 Décembre 2007
    #2
  3. Offline
    wild mTs ex membre
    wild mTs, 27 Décembre 2007
    #3
  4. Offline
    ailless Asimov, Sagan, Carlin, Hitchens
    ailless, 27 Décembre 2007
    #4
  5. Offline
    Inco Elite
    avant de commencer le code , ecris deja sur papier les conditions que doivent respecter les chiffres , comme dis pas de doublon, faut trouver l'alogritme ideal mais bon je pense qu il faut encore faire un autre histoire de savoir combien de chiffre tu va mettre et voir si c est possible de réaliser la grille...

    à mon avis avant de commence tu devais d 'abord commencer par chercher comment tu le ferais à la main déja une fois que tu as trouve l'algoritme t aura " plus qu a" le mettre en code
    Inco, 27 Décembre 2007
    #5
  6. Offline
    - Lo0 Elite
    Moi j'ai du le faire en C y'a deux ans

    J'ai retrouvé ca, je sais pas si ca vient de mon code finis ;d J'espere que ca poura t'aider. Ca cree donc une grille et sa compte le nombre d'essais nécessaire a la création. L'algoritme n'est pas tres éfficaces, mais ca fonctionne. Si je me souviens bien, ca invente un chiffre pour une case, puis vérifie qu'il respecte les conditions par apport aux autres chiffre déja mis en place. Si ca ne respecte pas les conditions, il en réinvente un jusqu'a avoir essayé les 9 chiffres différent, si aucun des 9 chiffres ne permet de continuer il recommence a 0.

    Code:
    int CreeGrilleSudoku (int *tab[][9] )
    {
    	int i, j, k, a,b,  redonne = 0, compteur = 1, essais = 0, essais2 = 0 ; // compteur = 1 car si réussi premier coup compte 0x 
    	Intro_Matrice_i_Aleatoire(9, 9, tab, 0, 0 ) ;
    	Affiche_Matrice_i(9, 9, tab ) ;
    	srand((unsigned) time(NULL) + rand());
    
    	for( i=0 ; i<9 ; i++ )
    		for ( j=0; j<9 ; j++ )
    		{
    			tab[i][j] = rand() % 9 + 1;
    			if ( j != 0 )
    			for( k = j-1 ; k >= 0 ; k-- ) 
    			{
    				if (tab[i][k] == tab[i][j] )  // A
    				{
    					redonne = 1 ;
    					k = 0 ;
    					printf("testKK" ) ;
    				}
    			}
    			 printf("test1") ;
    			if (redonne == 0 && i != 0)
    			{
    				printf("test2") ;
    				for( k = i-1 ; k >= 0 ; k-- )   // B
    				{
    					if (tab[k][j] == tab[i][j] )
    					{
    						redonne = 1 ;
    						k = 0 ;			// empeche de calculer pour rien, sort de la boucle
    						essais++ ;
    					}
    				}
    			}
    			if ( redonne == 0 && ( i!=0 || j!=0 ) )	   // C
    				for ( a = i - i%3 ; a < i - i%3 + 3 ; a++ )
    					for ( b = j - j%3 ; b < j - j%3 + 3 ; b++ )
    					{
    						if ( ( a != i || b != j ) && tab[a][b] == tab[i][j]) 
    						{
    							 redonne = 1 ;
    							 essais2++ ;
    							 a = 10 ;
    							 b = 10 ;
    							 printf( "test") ;
    						}
    					}
    				printf("tot %d", essais) ;
    
    
    
    			if(redonne == 1 )
    				j-- ;
    			//else if( redonne == 3 )
    			else if ( redonne == 0 ) 
    				essais = 0 ;
    			
    			redonne = 0 ;
    			if ( essais == MAXESSAIS || essais2 == MAXESSAIS )
    			{
    				printf("TOTO1") ;
    				Intro_Matrice_i_Aleatoire(9, 9, tab, 0, 0 ) ;
    				essais = 0 ;
    				essais2 = 0 ;
    				i = -1 ;
    				j = -1 ;
    				compteur++ ;
    			}
    			
    		Affiche_Matrice_i(9, 9, tab ) ;
    		}
    		Affiche_Matrice_i(9, 9, tab ) ;  // fonctionne pas
    			return compteur ;
    }
    - Lo0, 27 Décembre 2007
    #6
  7. Offline
    leprincemiri ex membre
    merci;)

    en fait, j ai deja les conditions qui verifient si le sudoku est bon (c etait une question d un exam) et mtn je fais le sudoku proprement dis.

    En effet, je ne regarde pas les codes que l on me donne, je deteste prendre les sources de qqun d autre
    leprincemiri, 27 Décembre 2007
    #7
  8. Offline
    Skarbone I would rather be snowboarding
    J'ai déja codé (en java pour ma part) un ptit truc qui sortait une grille de sudoku parmis une liste prédéfinie, puis nous permettait de la remplir et une fois remplie, vérifiait si il n'y avait pas de fautes.

    Ca, c'est pas trop dur.

    Apparemment, ce que tu cherches a faire, ca serait de créer une grille de sudoku a TOTALEMENT aléatoire a partir de rien?

    Crois moi, ca ne sera pas du tout aussi facile qu'on pourrait l'imaginer...

    Car tu peux très bien te dire "je place 15 chiffres aléatoirement, en vérifiant qu'ils sont tous cohérent les un par rapport aux autres"... Ca sera relativement facile, a mon avis en quoi, une petite centaine de ligne au plus ca devrait être torché?

    Mais en faisant cela, il y a deux problèmes:
    1) Est ce que grâce aux chiffres placés aléatoirement on peux trouver les autres chiffres, ceux qui manquent?

    2) Est ce qu'il n'existe qu'une et une seule solution pour ce sudoku?

    C'est surtout ces 2 choses la qui te poseront problèmes.




    Sinon, -Loo, dans ton code, ca ne serait pas plus simple d'utiliser un boolean pour "redonne" ?
    J'ai pas regardé avec attention, mais je pense que ca serait plus logique/simple


    Edit: Sinon, après avoir un peu réfléchi, je pense que pour régler ces problèmes, il faudrait en fait que le code génère une grille de sudoku completée et correcte, et qu'a partir de cette grille là, il enlève les chiffres que l'on pourrait trouver grâce aux autres, et ceci un a la fois, l'un après l'autre.

    Après avoir enlevé un chiffre, le code reessaye de trouver un chiffre que l'on pourrait trouver dans la "nouvelle" grille, cette "nouvelle" grille étant forcément la même que juste avant, moins le chiffre que l'on a enlevé :p.
    Une fois que l'ordinateur ne trouve plus de chiffre a enlever, on sort de la boucle, et notre grille de sudoku est prêtre a être completéeç

    De cette manière, on serait sur de pouvoir completer la grille, vu que les chiffres ne partirait que si on peux les trouver grace a d'autres chiffres...


    Franchement, je pense que c'est plutot comme ca qu'il faut raisoner. Maintenant, évidemment, faut trouver les bonnes conditions pour permettre d'enlever les "bons" chiffres de la grille, mais ca jte laisse chercher :cool:
    Skarbone, 27 Décembre 2007
    #8
  9. Offline
    - Lo0 Elite
    Mmmm ?

    Qu'il y ait plusieur solution possible pour une grille proposée, ce n'est pas grave. On utilise un algoritme qui se contente de vérifier s'il la grille completée est bien une grille de sudoku (idéalement, on réutilise une partie de la fonction permetant dans crée une)


    C'est une bonne question. Je penses que la est l'interet de cet exercice. Moi je l'ai pas fait dans cet optique, du coup, pour trouver une bonne grille, mon prog doit recommencer à zéro 10 000 fois. Le prog de ma prof trouvait ca en 10 essais :p-
    - Lo0, 27 Décembre 2007
    #9
  10. Offline
    Skarbone I would rather be snowboarding
    A ne pas oublier qu'en placant un certains nombres de chiffres plus ou moins au hasard, on peux très bien se retrouver avec une grille de sudoku insolvable.. Ce n'est pas parce que tous les chiffres placés aléatoirement sont corrects l'un par rapport aux autres qu'on pourra finir la grille...

    exemple: (x=case vide)

    xxx | xxx | xxx
    xxx | xxx | xxx
    xxx | x23 | xxx
    ------------------
    xxx | xxx | xxx
    xxx | xxx | xxx
    xxx | 3x2 | xxx
    ------------------
    xxx | 8xx | xxx
    xxx | xx1 | x2x
    3x2 | xxx | xxx

    Dans cette grille, les chiffres placés sont totalement cohérents. rien ne les empèches de se placer de cette facon, selon les règles du sudoku. Seulement, dans la case ou il y a un 8 (en bas au milieu), ou est ce qu'on pourrait placer le 2?

    Puis il me semble qu'en principe il ne peux y avoir qu'une et une seule solution possible pour une grille de sudoku donnée, vu que tu dois déduire la position d'un chiffre selon la position des autres chiffres.. Chaque chiffre que tu inscris ne peut être qu'a une seule place selon ce que tu a déduis, et ce nouveau chiffre placé va te permettre de déduire la position d'un ou de plusieurs suivants!

    Sinon, avec la plupart des codes que j'ai vu on pourrait très bien se retrouver avec une situation de ce genre:

    [1][.][.][.][.][.][.][.][.]
    [2][.][.][.][.][.][.][.][.]
    [3][.][.][.][.][.][.][.][.]
    [4][.][.][.][.][.][.][.][.]
    [5][.][.][.][.][.][.][.][.]
    [6][.][.][.][.][.][.][.][.]
    [7][.][.][.][.][.][.][.][.]
    [8][.][.][.][.][.][.][.][.]
    [9][.][.][.][.][.][.][.][.]

    Et puis la, quoi? qu'est ce qu'on pourrait faire? comme je l'ai dit, les chiffres qui sont placés ne permettent pas de remplir le sudoku completement :/.


    Franchement le problème est a mon sens bien plus compliqué qu'il n'y parait au premier abord :/
    Skarbone, 28 Décembre 2007
    #10
  11. Online
    THiBOo Elite
    Un sudoku tant que t'as une solution, ta grille est valable.

    Il faut donc que ton programme génère une grille valable (en plaçant donc tous les chiffres), mais n'affichera pas cette grille là mais plutôt une grille de jeu avec les chiffres partiellement cachés.

    Ne cherchez pas plus loin, c'est la solution la plus efficace et la plus valable qui soit. Il faut juste que vous "reteniez" la grille de jeu (celle vec les chiffres cachés) de départ, histoire de pouvoir permettre au joueur de réinitialiser sa grille s'il réalise qu'il part dans un mauvais chemin.
    THiBOo, 28 Décembre 2007
    #11
  12. Offline
    - Lo0 Elite
    Ta grille de sudoku n'est pas solvable tout simplement car tu ne pars pas d'une grille de sudoku :p

    Le truc, c'est de faire une grille complete et puis de masquer des chiffres aléatoirement. De la, tu pourras toujours trouver une solution

    Si tu veux ne pas crée les chiffres directment lors de la création de la grille, c'est faisable, mais ca va etre compliqué :p-

    Edit :

    Et

    Sinon, avec la plupart des codes que j'ai vu on pourrait très bien se retrouver avec une situation de ce genre:

    [1][.][.][.][.][.][.][.][.]
    [2][.][.][.][.][.][.][.][.]
    [3][.][.][.][.][.][.][.][.]
    [4][.][.][.][.][.][.][.][.]
    [5][.][.][.][.][.][.][.][.]
    [6][.][.][.][.][.][.][.][.]
    [7][.][.][.][.][.][.][.][.]
    [8][.][.][.][.][.][.][.][.]
    [9][.][.][.][.][.][.][.][.]

    Et puis la, quoi? qu'est ce qu'on pourrait faire? comme je l'ai dit, les chiffres qui sont placés ne permettent pas de remplir le sudoku completement :/.


    147 369 258
    258 147 369
    369 258 147

    471 693 582
    582 471 693
    693 582 471

    714 936 825
    825 714 936
    936 825 714

    Voila une solution :p:p
    - Lo0, 28 Décembre 2007
    #12
  13. Offline
    Skarbone I would rather be snowboarding
    Bah vi mais bon, la solution ici tu la trouve plus ou moins au hasard non?
    Quel est l'intéret d'une telle grille de sudoku? C'est censé te faire réfléchir ce jeu :D pas te faire t'amuser a remplir des cases avec des chiffres plus ou moins au hasard :p
    Skarbone, 28 Décembre 2007
    #13
  14. Offline
    Skarbone I would rather be snowboarding
    Et c'est ce que ton code fait?

    Si oui alors excuse moi, on a bien le même principe en tête :p
    Seulement moi je retirerais pas des chiffres au hasard ;)
    Skarbone, 28 Décembre 2007
    #14
  15. Offline
    - Lo0 Elite
    Oui
    Ah ok. Moi, je demandais a l'user combien de chiffre il voulait qu'on enleve et puis je les retirais au hasard.
    Mais, selon quel logique voudrais tu enlever un chiffre plutot qu'un autre alors ?
    - Lo0, 28 Décembre 2007
    #15
  16. Offline
    Skarbone I would rather be snowboarding
    Justement, c'est la que l'algorithe serait compliqué! mais a mon sens ca serait la facon la plus sûre de le creer.
    Skarbone, 29 Décembre 2007
    #16
  17. Online
    THiBOo Elite
    Je vois vraiment pas comment tu peux décider de retrirer tel ou tel chiffre et pas un autre, de plus cela n'a aucun sens o_O

    Le seul truc que tu peux faire c'est de décider selon le "niveau" du jeu (facile-moyen-difficile) de décider de retirer X chiffres par lignes ... Ce que tu dois de tte façon faire c'est limiter le nombre de chiffres retirer par ligne :)
    THiBOo, 29 Décembre 2007
    #17
  18. Offline
    Skarbone I would rather be snowboarding
    ....

    Si avec 2 chiffres on peux trouver le suivant, alors on peuc déduire quel chiffre on pourrait trouver avec 2 autres, c'est tout... Et le niveau n'a rien a voir avec le nombre de chiffres retirés...
    Skarbone, 29 Décembre 2007
    #18
  19. Offline
    leprincemiri ex membre
    je vais faire d'une manière beaucoup plus simple, je vais créer des grilles que j'enregistre sur des fichiers et je n'aurai qu a utilise une lecture sur fichier dans mon programme, comme ca il ne devra pas creer la grille lui meme :D
    leprincemiri, 4 Janvier 2008
    #19
Statut de la discussion:
Fermée.