Dans un premier temps, comme je le disais, et avant de gérer les cases noires, je vais faire une passe d'optimisations. En l'état, le programme s'affole très vite, les temps de calculs deviennent trop grand pour que le programme soit utilisable.

J'ai commencé par faire des mesures sur des tailles de grilles croissantes. Les temps réels mesurés n'ont que peu d'importance, ce qu'il faut voir, c'est la rapidité avec laquelle les courbes s'élancent vers l'infini.

La courbe bleue est la taille en case de la grille. La courbe rouge est le temps pris avec la révision actuelle du programme. La courbe grise est le temps pris avec une petite « optimisation ». Nous allons voir qu'elle n'est pas si intéressante que ça, mais comme elle ne coûte rien, nous pourrons la garder.

Avant de passer à l'optimisation en elle-même, d'autres constats :

• Une grille 5×4 sans l'optimisation est trop longue, j'ai coupé avant le résultat. Je ne sais donc pas s'il existe un résultat ;
• Une grille 5×5 avec optimisation est trop longue, j'ai coupé le programme après 5 heures de calculs. Je ne sais donc pas s'il existe un résultat ;
• Les grilles trouvées ont à chaque fois sur la première ligne le premier mot du dictionnaire pour la taille données. Autrement dit, les grilles trouvées n'ont pas cherché bien loin dans l'arbre des possibilités.

Grilles trouvées :

----
|AA|
|HI|
----

-----
|AAS|
|BEA|
|ARC|
|TAS|
-----

------
|ABAT|
|BAVA|
|BIEN|
|ELUT|
------

Et la première ligne de la grille 5×4 est ABATS.

Le deuxième constat montre bien en quoi l'optimisation ne va pas servir à grand chose : même avec celle-ci, la recherche dans l'arbre est tellement longue que le programme n'est pas capable de dire qu'il n'y a pas de réponse.

L'optimisation est toute bête, elle consiste à modifier le dictionnaire. En effet, on a vu dans l'état des lieux initial que le dictionnaire était implémenté de façon très bête : il répondait à une requête après un examen de l'intégralité des mots, ceux-ci étant stockés dans un bête tableau.

On pourrait être tenté de sauter sur le dictionnaire et de se lancer dans son optimisation. Patience ! Même si des idées viennent en tête, il y a peut-être des choses bien plus simples à faire avant.

Puisqu'il y a trop de mots dans le dictionnaire, abaissons ce nombre de mots en ne stockant aucun mots des tailles qui ne seront pas cherchées. Actuellement, le programme ne cherche que des grilles totales, il n'a donc besoin que des mots des tailles de la largeur et de la hauteur de la grille.

Plus tard, il y aura cependant, avec les cases noires, plusieurs tailles possibles. J'assouplis donc l'optimisation en ne chargeant dans le dictionnaire que les mots de taille entre les tailles extrêmes de la grille. Vu que je ne teste pour le moment que des grilles carrées ou avec une différence de 1 entre la hauteur et la largeur, cela revient au même que de ne charger que les mots nécessaires.

Oui, c'est une optimisation. Une optimisation de données. Il est inutile de garder avec nous des choses qui ne serviront pas. Cependant, cette optimisation n'a aucun impact sur une grille dont les mots peuvent être de taille entre 1 et la taille de mot la plus grande trouvée dans le dictionnaire. On n'optimise pas le pire cas. D'un point de vue strict, ce n'est pas une optimisation.

Cependant, cette optimisation ne coute rien. Ou pas grand chose. Ajouter un test au chargement du dictionnaire sur la taille des mots ne va pas alourdir le temps de chargement du dictionnaire de beaucoup. Et le code de l'exécution de la recherche, lui, n'a pas été touché.

Alors il serait dommage de ne pas garder cette optimisation.

Le code source pour cette optimisation n'est pas encore disponible.

À bientôt.