Je suis pour l'instant assez novice en C++ et j'essaie pour m'exercer de créer un jeu de Sudoku. Ça n'a rien à voir avec le concours c'est en fait le concours qui m'a donné l'idée, mais je m'y suis pris trop tard, et les aspects que je cherche à travailler sont la construction d'algorithme et l'architecture MVC...
Pour l'instant, j'en suis à la base... base de mon jeu assez basique, d'ailleurs. tout ce que je veux, c'est une grille de 9 x 9 cases, même pas quadrillée, mais dont les nombres sont modifiables à volontée, et que l'on peut vérifier après coup... Les grilles doivent se générer toutes seules et par après, 27 chiffres devront s'afficher dans la grille au départ... ces chiffres ne doivent pas être modifiables. par la suite, on s'occupera de vérifier si les chiffres sont correctement placés dans la grille. c'est là le cahier des charges que je me suis fixé...
J'ai commencé ma classe SudokuWidget qui affiche un QTableView, qui lui même affiche un QStandardItemModel. L'ennui, c'est que je ne sais pas comment générer ma grille de base!!
Je suis donc à la recherche d'une façon de faire en sorte de:
d'abord générer TOUTE une grille
Puis de n'en garder que 27 chiffres (3 par "bloc" (3 x 3 cases))
et finalement de conserver les coordonnées pour me souvenir de quelles cases sont des cases qui ne changent pas...
(si vous voyez un moyen différent de m'organiser pour qu'une case soit inmodifiable, faites!)
Tout ce que je souhaite avoir, ce sont des idées de "comment m'y prendre" je ne vous demande aucun code.
Le concours ayant créer une vague "codons un Sudoku", le forum est rempli de question à ce niveau.
J'ai d'ailleurs lu un sujet, il n'y a pas très longtemps, répondant à ta première question. Fais une recherche
Pour ta question suivante, tout dépend du niveau de difficulté.
En fonction des différents chiffre que tu gardes, la grille devient plus facile/difficile à résoudre. Tu dois donc définir clairement quels critères diminuent/augmentent la difficulté du jeux.
Une fois cette liste établit, il ne te restera qu'à appliquer tes critères.
J'irais avec une matrice (représentant la grille) de booléen. La case vaut true si la valeur est modifiable, false sinon.
Lorsque le joueur cherche à modifier la case, tu récupères les "coordonnées" de celle-ci et tu vérifies, via la table, si elle est modifiable.
Ou encore, tout juste avant le début du jeux (toujours avec la table), tu parcours chaque case. Si elle vaut false, tu "grises" la case (tout dépend de comment tu gères les cases, l'ajout de nombre, etc.)
Il n'existe pas d'algorithme de génération de grille de sudoku efficace. C'est-à-dire que les algorithmes utilisés actuellement vont bien pour des grilles 9x9 mais qu'il serait impossible de générer des grilles 100x100 de manière rapide.
Un algorithme assez simple à mettre en place est le suivant:
1) Créer une fonction qui sait résoudre une grille données quelque soit son état (0 à 81 cases remplies) et qui renvoit le nombre de solutions (ou en tout cas si il y en a 0, 1 ou plusieurs).
La génération se déroule alors ainsi:
1) tirer au hasard une dizaine de cases dans la grille et y mettre des nombres au hasard mais qui respectent quand meme les règles du sudoku.
2) Résoudre la grille. On obtient alors la grille solution. Il reste plus qu'à mettre des "trous"
3) On tire au hasard des positions dans la grille et on enlève le chiffre qui s'y trouvait. On cherche le nombre de solutions de la grille avec le trou. Si il y en a 0, tu as une erreur, si il y en a 1 alors c'est bon, si il y en a plus que 1, alors on remet le chiffre qu'on a enlevé.
4) On recommence le point 3 jusqu'à ce qu'on ait testé une fois chaque case ou que tu ais envie d'arrêter l'algorithme parce que tu juges qu'il y a assez de trous.
Cet algorithme crée des grilles en moins de 1s sans problème. Si on le laisse faire, il génère des grilles très difficiles. J'ai eu trouvé des grilles avec seulement 19 chiffres dans la donnée (La meilleure grille connue à ce jour n'en a que 17), ce qui est largement au-dessous des grilles "diaboliques" des journaux qui en ont habituellement entre 28 et 30.
Les grilles générées ne sont cependant pas "jolies" dans le sens où dans les journaux, les grilles ont souvent un (ou plusieurs) axes de symétries. Ces axes n'aident en rien à la résolution, mais apperement c'est visuellement plus attrayant pour l'humain.
La difficulté d'une grille dépend du nombre de chiffres présents (moins y en plus c'est dur) mais aussi des techniques à mettre en place pour arriver à la solution. Tu peux classifier ta grille dans une catégorie de difficulté en comptant le nombre des cases occupées et en regardant quelles techniques utiliser pour la résoudre (Wikipédia). Par contre pour générer directement une case de difficulté donnée, je ne sais pas comment faire.
Pour ce qui est de résoudre la grille, plusieurs possibilités existent. La première est de faire "comme un humain", cest-à-dire en utilisant les tests que font les joueurs quand ils résolvent (?) une grille. Wikipédia donne une liste de ces techniques. C'est intéressant à coder et ça permet de montrer à l'utilisateur quel nombre il aurait pu trouver. Ce n'est par contre pas facile à mettre en place.
Une deuxième possibilité est de faire "comme une machine", c'est-à-dire aller dans la première case vide mettre un 1, aller dans la deuxième, mettre un 2 et ainsi de suite. Si tout à coup il y a un chiffre qu'on ne peut pas mettre dans une case, alors on revient en arrière et on augmente la valeur de la case de 1 et on continue comme avant.
Cette méthode est également intéressante à coder puisqu'on peut utiliser la récursivité pour résoudre ce problème.
Pour ce qui est des structures de donnée, j'avais imaginé la solution suivante. Une classe "Matrice" qui représente un tableau 2D carré de taille fixe. (En-dedans il y avait un std::vector<> mais c'est pas la seule solution) Ensuite j'utilisais 4 matrices 9x9. Une contenant la grille en elle-même avec des 0 pour les cases vides. Ensuite j'avais une matrice de booléen qui contenait les informations permettant de savoir si un chiffre est déjà présent sur une ligne/colonne/case donnée. Par exemple, Colonne[2][3] permet de savoir si le chiffre 4 (3+1) est déjà présent sur la colonne 3 (2+1). Et chaque fois que l'on modifie la grille "principale", on met à jour les grilles annexes. Cela permet d'éviter de faire des tests compliqués pour savoir si un nombre donné est déjà présent sur une ligne/colonne/case donnée. Il suffit de lire ces tableaux annexes.
J'espère que ça éclaire certains points. N'hésite pas à redemander si nécessaire.
Bonjour, Nanoc a déjà presque tout dit, je vais rajouter quelques astuces:
* d'abord générer TOUTE une grille
--> RQ Si tu connais une grille il y a des opérations matématiques comme échanger deux colonnes d'un bloc de 3, échanger deux lignes d'un bloc de 3, remplacer tous les 7 par des 9 et inversement (en fait échanger 2 chiffres), faire une symétrie (axiale ou centrale). qui te permettent de faire de "nouvelles" grilles à partir de l'ancienne qui lui sont mathématiquement identiques. Ces nouvelles grilles sont de difficulté identique à la grille de base, et sont capable de bluffer le joueur qui pense en résoudre de nouvelles à chaque fois.
* et finalement de conserver les coordonnées pour me souvenir de quelles cases sont des cases qui ne changent pas
--> Voila ce que j'ai fait : je code de 0 à 8 les cases qui changent et de 9 à 17 celles qui ne changent pas, pour avoir la valeur a afficher je fais : case%9 +1. Je ne suis pas convaincu que ce soit la meilleure méthode, mais ca marche.
Alors là, j'ai l'embaras du choix, semble-t-il... Je commence à trouver des idées comme des méthodes privées du genre switch(int num, int num2) qui pourraient changer tous les "num" en "num2" à partir d'une grille et faire des sélections aléatoires de 10 switch() à effectuer... je pourrais aussi faire une fonction envers() qui renverse la grille, et que j'appliquerais selon une sélection aléatoire... ainsi je pourrais, partant de la même grille, en faire tou plein de différentes...
Mais j,aimerais quand même avoir votre point de vue sur ces idées...
EDIT: Quelles techniques puis-je utiliser pour obtenir un nombre aléatoire en C++? la méthode de Mateo du cours de C fonctionnera-t-elle?
Ici tu n'est pas en train de faire une appli critique, n'importe quelle méthode aléatoire est bonne. Moi pour les jeux j'en utilise une qui est rigolote celle du jeu Worms:
Je demande au joueur de me donner un nom (son nom, un nom de code ...)
Je calcule un hash dessus (le premier pour lequel je trouve une librairie, le choix n'est pas critique), j'utilise ce hash comme ensemble de valeurs aléatoires pour générer mon niveau.
En vrai c'est pas aléatoire, en vrai c'est totalement déterministe, mais c'est rigolo, car comme ca rien qu'en retenant le nom d'un niveau on peut le faire, le passer à ses copains autant de fois qu'on veux facilement.
z'êtes vraiment sympa, tous autant que vous êtes, d'avoir répondu!!! Maintenant, j'ai l'algo qui me génère les grilles, et puis celui qui choisit lesquelles cases seront remplies sur la grille au départ... Mais il me manque un truc encore: c'est quoi une matrice? ( Ah je vous avais dit que j'étais tout à fait novice!!! Je vais quand même avancer une hypothèse: ) est-ce que c'est un tableau multi dimensionnel? ou si c'est autre chose? (ah et encore là, si j'ai raison de penser que c'est un multidi, n'allez pas croire que je sais les créer... en PHP, j'y arrive, mais en C++...)
Pour déclarer une matrice statique, pas de problème particulier.
Par exemple, pour une matrice de 9*9 (comme une grille de Sudoku) :
int grilleSudoku[9][9] = {{0}};
Ce code crée une matrice de 9 lignes (le premier 9) de 9 colonnes. Toutes les cases sont initialisées à 0.
Si tu veux initialiser le tableau directement :
Dans ce cas, un vector n'est pas vraiment nécessaire (puisqu'il n'y aura jamais de changement de taille, etc.) Mais c'est toujours une bonne habitude à prendre d'utiliser (trop!) les vector.
std::vector< std::vector< int > > grilleSudoku(9,std::vector<int> (9,0));
Ha! Lala!!! J'en viens à bout!!! Je vous explique comment je fais: j'initialise une grille de départ que je connais, qui est très simple.
ensuite, je fais une série d'un nombre aléatoire (entre 15 et 40) interversions entres des nombres aléatoirement choisis à chaque fois (j'espère que c'est assez clair)
Ça me donne la grille corrigée. puis, je me fais une matrice (hourra, j'ai casé le mot) qui retiens les cases qui seront remplies et inmodifiables (une matrice de bool) et puis je fais une boucle pour initialiser la grille du joueur.
C'est ce qui met définitivement fin à ce questionnement précis; je sais maintenant ou je m'en vais...
EDIT: Aïe ! Comment on attribue une matrice dynamiquement?
est-ce que c'est comme ça
Ha! Lala!!! J'en viens à bout!!! Je vous explique comment je fais: j'initialise une grille de départ que je connais, qui est très simple.
ensuite, je fais une série d'un nombre aléatoire (entre 15 et 40) interversions entres des nombres aléatoirement choisis à chaque fois (j'espère que c'est assez clair)
Ça me donne la grille corrigée. puis, je me fais une matrice (hourra, j'ai casé le mot) qui retiens les cases qui seront remplies et inmodifiables (une matrice de bool) et puis je fais une boucle pour initialiser la grille du joueur.
C'est ce qui met définitivement fin à ce questionnement précis; je sais maintenant ou je m'en vais...
EDIT: Aïe ! Comment on attribue une matrice dynamiquement?
est-ce que c'est comme ça
bool **matrice;
matrice = new bool[9][9];
?
Je rééditerai ce message quand j'aurai essayé...
Non. De un, tu n'as pas besoin de l'allouer dynamiquement (tu as un nombre de case connu et défini lors de la déclaration de ton tableau).
Ensuite, si tu voulais l'allouer dynamiquement, il serait préférable d'utiliser les vector (que tu peux d'ailleurs utilisé, même si tu ne l'alloues pas dynamiquement).
@MohamedAbdallah32 Bonsoir, merci de ne pas squatter le sujet résolu des autres, créer votre propre sujet dans le respect des règles du forum à savoir qu'un message commence par des règles de politesses (Un bonjour ou des salutations à la communauté et se termine par des remerciements par avances pour les futures réponses), la description de votre problème et le code que vous avez écrit inséré sur le forum à l'aide de l'outil d'intégration de code soit le bouton code </>.
Avant de poster un message, vérifiez la date du sujet dans lequel vous comptiez intervenir.
Si le dernier message sur le sujet date de plus de deux mois, mieux vaut ne pas répondre. En effet, le déterrage d'un sujet nuit au bon fonctionnement du forum, et l'informatique pouvant grandement changer en quelques mois il n'est donc que rarement pertinent de déterrer un vieux sujet.
Au lieu de déterrer un sujet il est préférable :
soit de contacter directement le membre voulu par messagerie privée en cliquant sur son pseudonyme pour accéder à sa page profil, puis sur le lien "Ecrire un message"
soit de créer un nouveau sujet décrivant votre propre contexte
ne pas répondre à un déterrage et le signaler à la modération
* Un wrapper C++ pour sqlite * Une alternative a boost units
* Un wrapper C++ pour sqlite * Une alternative a boost units