Exposé n° 87 : L’ordinateur face au Sudoku et autres jeux

Le jeu du sudoku est un jeu très populaire qui s’adresse à tous : les règles en sont très simples. Pourtant, il est parfois difficile voire diabolique à résoudre. Il soulève des questions intriguantes dont certaines ne sont, aujourd’hui, pas encore résolues. Combien de grilles différentes du sudoku peuvent être construites ? Quel est le nombre minimum de cases à remplir au départ afin d’aboutir à une solution qui soit unique ? Est-ce un jeu facile à résoudre pour l’ordinateur, même avec des grilles plus grandes ? L’ordinateur peut-il nous aider à résoudre d’autres jeux, comme le jeu de sokoban ? Existe-t-il des jeux qui sont de véritables casse-têtes pour l’ordinateur ? Dans cet exposé nous aborderons ces questions mathématiques et informatiques dans le but d’illustrer les limites de l’ordinateur.

Exposé proposé par Véronique Bruyère.