Morpion Solitaire - Problème NP-Hard

Morpion Solitaire - Problème NP-Difficile

Erik D. Demaine, Martin L. Demaine, Arthur Langerman, Stefan Langerman

Même s'il est très facile de jouer au Morpion Solitaire, il est prouvé que ce jeu est NP-hard (NP-difficile en français) et même que son plus haut score n'est pas approximable, à moins que P=NP. Une équipe de quatre personnes, Erik D. Demaine, Martin L. Demaine (tous deux du MIT, USA), Arthur Langerman (Langerman Diamonds, Belgique) et Stefan Langerman (Université de Bruxelles, Belgique) a prouvé ce théorème dans leur article "Morpion Solitaire" initialement publié en 2004, puis à nouveau dans la version améliorée de Theory of Computing Systems publiée en 2006 :

Théorème 2. Pour tout k ≥ 3, il est NP-hard de trouver la plus longue partie démarrant d'un motif initial de n points, ou même de trouver une partie d'une longueur à moins de n^1-ε de la plus longue partie, pour toute constante ε > 0. Ce résultat est valable pour les deux variantes du jeu.

Dans leur article, k est le nombre de segments dans une ligne (joignant k+1 points). Et n est le nombre de points du motif initial. Les deux variantes dont ils parlent sont les modèles Touchant et Disjoint. Cela signifie que les valeurs de k et n sont, selon le jeu :

Jeu		k	n
5	T	4	36
	D
4	T	3	24
	D

Leur démonstration est valable pour tout motif initial général, une croix grecque ou non. Attention toutefois, on peut quand même connaître la meilleure partie dans certains cas particuliers : exemple facile, à partir d'un motif initial de n = k points alignés, le meilleur score est de un seul coup. Ou par exemple à partir de ce motif de 7 points, on peut avoir un score infini. Et l'on connaît maintenant les meilleures parties possibles aux jeux 4T et 4D. Pour plus de détails sur ce qu'est un problème NP-difficile, voir http://en.wikipedia.org/wiki/NP-hard ou http://mathworld.wolfram.com/NP-HardProblem.html

Les pages des quatre auteurs sont :

George Bell, l'auteur d'un site intéressant sur le jeu voisin du Solitaire, http://home.comcast.net/~gibell/pegsolitaire, m'a envoyé une amusante remarque : l'article ci-dessus est probablement le seul article mathématique jamais écrit par deux paires de père et fils ! Mais peut-être quelqu'un connaît un autre exemple ?

Erik D. Demaine, avec Robert A. Hearn, ont publié en 2009 le livre "Games, Puzzles, and Computation" aux éditions A. K. Peters Ltd, maintenant partie de CRC Press : http://www.crcpress.com/product/isbn/9781568813226. Le jeu du Morpion Solitaire est présenté page 180.