Quand les ordinateurs jouent aux casse-têtes

Tout le monde connaît au moins quelques casse-têtes logiques en forme de grille que l’on trouve sous différentes formes et variantes dans les journaux ou les magazines. Le puzzle logique le plus populaire est sans doute le Sudoku, un jeu japonais inspiré du carré latin, connu depuis plusieurs siècles. Un autre exemple est le problème des huit dames, qui consiste à placer huit dames sur un échiquier de manière qu’aucune dame ne puisse en prendre une autre. Mais comment ce type de puzzle peut-il être généré automatiquement, et comment un ordinateur peut-il trouver automatiquement toutes les solutions pour un puzzle donné ? Dans cet atelier, nous présentons de manière visuelle et conviviale une solution basée sur la programmation par contraintes. Elle consiste à modéliser les règles du jeu sous forme de contraintes, et à utiliser un moteur de résolution de contraintes pour générer des solutions. Cette approche est souvent utilisée en informatique et en intelligence artificielle pour résoudre des problèmes non triviaux.