Le «Scrabble®»

Le jeu de Scrabble a été conçu dans les années trente par l'Américain Alfred Mosher Butts (1900-1993). Cet architecte New-Yorkais venait d'être contraint au chômage par la fameuse crise de 1929 quand il lança la première version de son jeu - alors dénommée Lexico. Il avait soigneusement calculé la répartition des lettres parmi les 100 jetons sur la base d'une analyse statistique d'un exemplaire du New York Times.

La petite applet ci-dessous émule un jeu de Scrabble. Le but n'est bien entendu pas de rivaliser avec des logiciels tels que PC-Scrabble, mais simplement de montrer qu'en utilisant un type de données abstrait adapté, la programmation de ce jeu ne pose pas de gros problèmes (du moins tant qu'on se limite à un dictionnaire relativement petit, ici moins d'un millier de mots). Utilisez le "drag & drop" pour placer des jetons sur les cases (ou pour les remettres dans le "pot") et validez votre coup à l'aide du bouton "Ok". Le joueur "humain" porte un prénom choisit aléatoirement tandis que l'ordinateur s'appelle "LWH".

L'essentiel de la technique employée réside dans l'utilisation d'une structure de donnée arborescente appellée Arbre lexicographique généralisé. Dans l'illustration ci-dessous, les lettres terminales d'un mot sont colorés en rouge. Cet arbre code donc les mots «A», «AN», «ANE», «AME», «AMIS», «BAT», «BATEAU», «BAS», «BASSE», «BASSES» etcaetera. Cette structure permet de vérifier très rapidement si un mot existe dans le dictionnaire, ou si un mot peut être écrit à partir d'un ensemble de lettres. A partir de ces deux "services" de base, on peut rechercher tous les mots s'écrivant avec un ensemble de caractères et qui respectent certaines règles : longueur minimale et maximale, lettres imposées à une position etc.

Ce type de structure arborescente est généralement utilisée dans les compilateurs pour codifier la liste des identifiants autorisés et dans des outils tels que les correcteurs orthographiques.

LOEWENGUTH Pascal - http://lwh.free.fr -