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 -