sudoku C++

Statut
N'est pas ouverte pour d'autres réponses.
L

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

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

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

- 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 ;
}
 
1er
OP
L

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
 
Skarbone

Skarbone

Le méchant Ω
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é ^^.
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:
 
- Lo0

- Lo0

Elite
Mmmm ?

2) Est ce qu'il n'existe qu'une et une seule solution pour ce sudoku?
Cliquez pour agrandir...
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)


1) Est ce que grâce aux chiffres placés aléatoirement on peux trouver les autres chiffres, ceux qui manquent?
Cliquez pour agrandir...
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 ^^-
 
Skarbone

Skarbone

Le méchant Ω
- Lo0 a dit:
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)
Cliquez pour agrandir...
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 :/
 
THiBOo

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

- Lo0

Elite
Skarbone a dit:
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?
Cliquez pour agrandir...
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é ^^-

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
 
Skarbone

Skarbone

Le méchant Ω
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 ^^
 
Skarbone

Skarbone

Le méchant Ω
- Lo0 a dit:
T
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é ^^-
Cliquez pour agrandir...
Et c'est ce que ton code fait?

Si oui alors excuse moi, on a bien le même principe en tête ^^
Seulement moi je retirerais pas des chiffres au hasard ;)
 
- Lo0

- Lo0

Elite
Skarbone a dit:
Et c'est ce que ton code fait?

Si oui alors excuse moi, on a bien le même principe en tête ^^
Cliquez pour agrandir...
Oui
Seulement moi je retirerais pas des chiffres au hasard ;)
Cliquez pour agrandir...
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 ?
 
Skarbone

Skarbone

Le méchant Ω
- Lo0 a dit:
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 ?
Cliquez pour agrandir...
Justement, c'est la que l'algorithe serait compliqué! mais a mon sens ca serait la facon la plus sûre de le creer.
 
THiBOo

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 :)
 
Skarbone

Skarbone

Le méchant Ω
THiBOo a dit:
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 :)
Cliquez pour agrandir...
....

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...
 
1er
OP
L

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
 
Statut
N'est pas ouverte pour d'autres réponses.
Haut