Et en C++ ?
06/08/2020
La comparaison entre VBA, Phyton, PHP ou C restait dans un style procédural. Et si on s'aventurait dans l'orienté objet ?
Allez changeons de paradigme, attention c'est bestial :
Zou, en Orienté Objet !
On pourrait transcrire le code en C quasi directement en C++. Après tout, les méthodes des objets sont écrites dans un langage procédural. Mais ce serait sans intérêt et contraire à la philosophie de l'orienté objet. En OO, l'approche quitte nécessairement le procédural pour aller dans le conceptuel...
Comment un développeur OO voit une grille de sudoku ? Comme ça :
C'est à dire sous la forme de 9 régions, elle-même composées de 9 valeurs ; un embryon de structure fractale. On définit alors deux classes :
- une classe pour les régions,
- une classe pour la grille d'un sudoku.
La classe Region
Une instance de la classe Region contient quelques attributs privés :
- une grille de 3x3 valeurs comprises entre 0 et 9
- une position d'une case courante dont les coordonnées en ligne, colonne sont mémorisées par deux entiers l et c.
Et quelques méthodes triviales (c'est à dire dont les noms devrait suffire à évoquer leurs fonctions), à quelques exceptions près :
- suivante() passe la case courante à la position suivante et retourne un booléen "vrai" si on atteint la dernière case ou "faux" sinon,
- teste(v) vérifie si la valeur v est adaptée à la position courante,
- ajoute(v) affecte la valeur v à la position courante et passe celle-ci à la case suivante,
- dup() crée une copie d'une instance,
- val(l,c) retourne la valeur de la grille privée en ligne l et colonne c (indépendamment de la case courante).
La classe Grille
La classe Grille est à peine plus complexe.
Son constructeur commence par dresser la liste de toutes les régions possibles :
______#0 ______#1 1 2 3 4 5 6 7 8 9 ______#2 1 2 3 4 5 6 7 9 8 ______#3 1 2 3 4 5 6 8 7 9 ... ______#362879 9 8 7 6 5 4 3 1 2 ______#362880 9 8 7 6 5 4 3 2 1
Il n'y en a que 9! (plus une pour la région vide, une quantité négligeable pour le développeur OO) dont le nombre est mémorisé dans l'attribut publique nbRegions et chaque cas possible dans le tableau Regions de pointeurs sur des instances de la classe Region. C'est la méthode privée listeRegions() qui est chargée de renseigner la liste des régions possibles.
Par ailleurs, la classe Grille contient quelques attributs et méthodes privés :
- un tableau de 3x3 régions choisies chacune parmi les 362 881 régions possibles,
- une grille de 9x9 valeurs comprises entre 0 et 9 qui correspondent au choix des 9 régions, mise à jour grâce à la méthode privée enGrille(),
- les contraintes à respecter pour le sudoku recherché,
- une position d'une case courante dont les coordonnées en ligne, colonne sont mémorisées par deux entiers l et c.
Les méthodes publiques de la classe Grille font ce que leur nom exprime, valide(r) étant l'équivalent de teste(v) de la classe Region.
La beauté d'un code OO
Une fois ce travail préliminaire effectué, la recherche d'une solution pour un sudoku est spectaculairement concise et lisible :
Les horreurs cachées
L'envers du décor l'est beaucoup moins.
Un travail considérable
Même en se contentant de l'encapsulation de l'approche OO (on laisse de coté les notions d'héritage et de polymorphisme), les 113 lignes de code de la solution en C sont remplacées par 365 lignes réparties en 5 fichiers (region.h, region.cpp, grille.h, grille.cpp et sudoku.cpp).
Un résultat lamentable
Les toutes dernières version de Python, PHP et C++ n'étant pas disponibles sur le serveur utilisé pour les tests de performance de l'article précédent, on les refait sur un serveur fraichement installé (Centos 8 en l'occurrence) :
- 3 s en Python3,
- 1 s en PHP 7,
- 0,04 s en C,
- 45 s en C++ !
A propos, la première solution trouvée en C++ est différente de celles trouvées dans les autres langages :
2 1 4 3 6 5 8 9 7 3 5 6 7 8 9 1 4 2 7 8 9 1 4 2 3 5 6 4 9 5 2 1 7 6 3 8 8 2 7 9 3 6 4 1 5 1 6 3 8 5 4 7 2 9 6 7 2 4 9 1 5 8 3 5 3 1 6 2 8 9 7 4 9 4 8 5 7 3 2 6 1
Voilà un très bel exemple pour la loi de Less :-)
Conclusion
Il ne faudrait surtout pas jeter le bébé avec l'eau du bain : en déduire que l'approche orienté objet serait inefficace serait une grave erreur !
Car ici, dans le cas particulier de la résolution d'un sudoku, elle est inadaptée. C'est un problème trop simple.
Pour d'autres situations plus complexes, l'approche orienté objet apporte bien au contraire une vision salvatrice, comme suggéré par la simplicité du code principal de résolution d'un sudoku en C++.
Sans oublier que les programmes conçus pour ces tests sont certainement perfectibles.
(Sources des exemples de code sur demande)