La diffraction des rayons X est une technique de sondage de la matière permettant d'accéder à l'organisation de la structure en récupérant une figure de diffraction créée par irradiation d'un objet aux rayons X. En utilisant des rayons X doux, moins énergétiques, il est possible d'appliquer cette technique à l'univers de la matière vivante.


La figure de diffraction donnée par l'objet est en fait sa projection dans l'espace des fréquences spatiales ou espace de Fourier. Chaque fréquence spatiale correspond à une orientation de l'onde des rayon X diffractés par un point, cette onde possédant une phase et une amplitude significatifs de la position du point dans l'objet et de son contraste.

Pour reconstruire l'image de l'objet à partir des fréquences spatiales, il suffit en théorie de réaliser la projection de la figure de diffraction dans l'espace réel. Mais pour obtenir une image nette et contrastée, il faut connaître avec précision la phase de chaque onde diffractée qui donnera le renseignement sur la position relative du point, l'amplitude étant directement asservie sur celle mesurée par un détecteur matriciel.

Des chercheurs ont alors employé un algorithme particulier appelé difference-MAP qui consiste en une série de considérations probabilistes discrètes. Celui-ci permet de résoudre des problèmes complexes mais n'ayant que deux contraintes.

Dans le cas de l'imagerie de diffraction, la première contrainte est également la plus simple : il s'agit de l'amplitude des ondes données par le capteur ; la seconde est un pendent de la théorie sur l'imagerie de diffraction : en dehors de l'objet, tous les pixels doivent être nuls. De cette manière, il a été possible de réaliser une image par microscopie de diffraction des rayons X sur des cellules à une résolution dépassant les instruments optiques classiques.

Mais quel est donc le rapport avec le Sudoku, ce jeu devenu le nouveau passe temps favoris de millions de personnes ? Et bien figurez vous que ce jeu semblant de prime abord un véritable casse tête n'est en fait qu'un problème très simple à deux contraintes. La première consiste à ce que chacun des neufs chiffres de 1 à 9 ne puissent être employé qu'une seule fois par ligne et apparaît neuf fois dans la grille totale. De plus, chacun des chiffres ne peut être employé qu'une seule fois dans chacune des sous grilles de neuf cases composant le jeu. De ce fait, en employant l'algorithme de difference-MAP, il est possible de résoudre absolument toutes les grilles de Sudoku, de la plus simple à celles montrant les difficultés les plus extrêmes.

En revanche, l'application de l'algorithme n'est pas triviale...

Sources: De la biologie au Sudoku, PNAS : publication complète en accès libre (anglophone), Article audio

tout_pour_la_science   4092   1   7/03/2006