mamiemando 22 sept. 2009 à 02:26
messages <3>, <4>, <5>
Je sais pas si c'est l'heure ou si je perds patience, mais ça fait deux fois de suite que je tombe sur un fil de discussion C++ ou les réponses n'ont RIEN à voir avec la question posée. On est pas ici pour raconter sa vie ou discuter du sujet c'est dingue ça !
@dna.factory
Alors NON un sudoku n'est pas compliqué à programmer si on sait écrire des boucles for. D'autant plus qu'il n' y a pas le solveur à programmer. Il suffit juste de réfléchir deux minutes avant de se lancer.
Chaque case peut contenir une valeur de 0 à 9 (son domaine). Ce domaine est restreint par les cases du cadran, de la ligne et de la colonne. Je te donne la méthode en pseudo code pour qu'il te reste un peu de pain sur la planche. Le sudoku usuel contient 3x3 cadrans de 3x3 cases chacuns (n=3).
Pour chaque case (i,j) de la grille
Si le domaine de la case(i,j) est réduit à un élément : le placer
Sinon : tirer une valeur v au hasard parmi les valeurs encore dans le domaine
Pour chaque case de la ligne i : supprimer la valeur v du domaine
Pour chaque case de la colonne j : supprimer la valeur v du domaine
Pour chaque case du carré n x n contenant (i,j) : supprimer la valeur v du domaine
Fin pour
A mon humble avis, les gens qui disent c'est pas à sa portée s'égarent franchement. La vérification est plutôt plus simple. La seule "difficulté" consiste à associer une case (i,j) avec un cadran (mais bon c'est pas la mort)
#define n 3 // sudoku 3x3 cadrans de 3x3 cases
// Associer chaque case (ligne,colonne) à un index qui identifie un cadran
// (le cadran en haut à geuche a pour 0, celui à sa droite 1 etc...) ce qui donne
// ce mapping pour n = 3 :
// 000111222
// 000111222
// 000111222
// 333444555
// 333444555
// 333444555
// 666777888
// 666777888
// 666777888
// Retourne l'identifiant du cadran contenant la case (ligne, colonne)
unsigned coordonnees2cadran(unsigned ligne,unsigned colonne){
if (ligne >= n*n) throw;
if (colonne >= n*n) throw;
return (ligne/n)*n + colonne/n; // '/' : division euclidienne
}
Pour vérifier une grille :
Vider les domaines associés à chaque ligne
Vider les domaines associés à chaque colonne
Vider les domaines associés à chaque cadran
Pour chaque ligne i
Pour chaque colonne j
Ajouter la valeur de la case(i,j) dans le domaine de la ligne(i)
Ajouter la valeur de la case(i,j) dans le domaine de la colonne(j)
Ajouter la valeur de la case(i,j) dans le domaine de du cadran contenant (i,j)
Fin pour
Fin pour
Pour chaque ligne i
Si le domaine de la ligne(i) ne contient pas les 9 valeurs : retourner faux
Fin pour
Pour chaque colonne j
Si le domaine de la colonne(j) ne contient pas les 9 valeurs : retourner faux
Fin pour
Pour chaque cadran
Si le domaine du cadran ne contient pas les 9 valeurs : retourner faux
Fin pour
Retourner vrai
Pour générer une grille à remplir par l'utilisateur tu génères simplement une solution et tu vires des valeurs. Par exemple 5 ou 6 valeurs par cadran. Dans certains cas peut être que la grille aura plusieurs solution mais ça n'a pas d'importance, puisqu'au final la fonction de vérification ne contrôle pas si la grille de départ et la solution proposée concordent, elle regarde juste si la grille proposée est valide.
Maintenant il ne te reste plus qu'à coder tout ça ;-) Si tu es motivée tu peux facilement voir que le pseudo code que je te propose marche pour des sudokus n x n cadrans de n x n éléments (avec n >=1 et pas seulement n = 3).
En terme d'implémentation tu peux par exemple utiliser des structures dans ce genre :
#include <vector>
typedef std::vector<bool> domaine_t;
struct case_t{
domaine_t domaine; // pour générer la grille ou pour le solveur
unsigned valeur;
};
typedef std::vector<std::vector<case_t> > grille_t;
Ce qui aurait été dur, ça aurait été :
1) de devoir coder un solveur. Mais en fait ça se fait très facilement avec un modèle CSP (voir cours de recherche opérationnelle pour les amateurs) qui comme la méthode que je viens de proposé est basée sur des réductions de domaines. Il est assez simple de vérifier si la grille a une ou plusieurs solution (avec un arbre de branchement).
2) de devoir générer des grilles à solution unique (mais une fois le solveur codé, il suffit de virer des valeurs et de n'autoriser leur suppression que si la solution reste unique).
Bonne chance
Lis ça, ça vient de ccm.net
