sudoku C++

leprincemiri · 27 Déc 2007

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 · 27 Déc 2007

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.

wild mTs · 27 Déc 2007

hop

http://www.cppfrance.com/recherche.aspx?r=sudoku

ailless · 27 Déc 2007

wild mTs a dit:
hop

http://www.cppfrance.com/recherche.aspx?r=sudoku

Je suis pas convaincu que lui donner des codes sources (codés à l'arrache) vont l'aider mais bon

bonne chance

Inco · 27 Déc 2007

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 · 27 Déc 2007

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 ;
}

leprincemiri · 27 Déc 2007

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 · 27 Déc 2007

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

- Lo0 · 27 Déc 2007

Mmmm ?

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

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?

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 · 28 Déc 2007

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

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 · 28 Déc 2007

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 · 28 Déc 2007

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?

Ta grille de sudoku n'est pas solvable tout simplement car tu ne pars pas d'une grille de sudoku

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

Skarbone · 28 Déc 2007

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

pas te faire t'amuser a remplir des cases avec des chiffres plus ou moins au hasard

Skarbone · 28 Déc 2007

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

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 · 28 Déc 2007

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

Oui

Seulement moi je retirerais pas des chiffres au hasard

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 · 29 Déc 2007

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

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 · 29 Déc 2007

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

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 · 29 Déc 2007

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

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

....

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

leprincemiri · 4 Jan 2008

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

sudoku C++

leprincemiri

ex membre

the_quent1

Elite

wild mTs

ex membre

ailless

Asimov, Sagan, Carlin, Hitchens

Inco

Elite

- Lo0

Elite

leprincemiri

ex membre

Skarbone

Le méchant Ω

- Lo0

Elite

Skarbone

Le méchant Ω

THiBOo

Elite

- Lo0

Elite

Skarbone

Le méchant Ω

Skarbone

Le méchant Ω

- Lo0

Elite

Skarbone

Le méchant Ω

THiBOo

Elite

Skarbone

Le méchant Ω

leprincemiri

ex membre

Autres sujets récents