Solitaire en croix

[Juzo]

Bonjour,

Je voulais vous parler d'un sujet très joli qu'on m'a transmis récemment, et qui vient d'un article de Pour la Science de janvier 1995.

Avant de rentrer dans le vif du sujet dans un autre fil, je vous propose ici un problème préliminaire.

On considère un damier cruciforme du jeu du solitaire.
La règle de déplacement est celle du solitaire : un pion peut se rendre sur un case vide située à 2 cases de sa position, en sautant par-dessus un pion adjacent qui est alors éliminé du plateau. Ce déplacement n'est possible qu'horizontalement ou verticalement (pas en diagonale).

Le défi est de savoir s'il est possible en appliquant la règle de déplacement de passer de la configuration où toutes les cases sont occupées sauf une croix au centre, à la configuration opposée où toutes les cases sont vides sauf une croix occupée au centre (voir image).

Il faut donc démontrer que cela est possible, ou démontrer que c'est impossible.

Je donnerai plus tard un indice sur la méthode à utiliser. Ce qui m'intéresse en attendant c'est la démarche que vous proposerez pour mathématiser le problème.

"Faux indice" : en attendant le vrai indice, vous pourrez toujours aller prier dans un temple bouddhiste en Chine.

Solitaire 1.png
-----

[MissJenny]

A mon avis pour montrer que c'est possible il faut produire l'algorithme (la suite de coups) qui mène de la configuration initiale à la configuration finale, je ne pense pas qu'il y ait une autre méthode de preuve. De l'autre côté pour prouver que c'est impossible, il suffit par exemple de trouver un invariant (un nombre qui ne change pas au cours du jeu) qui serait différent dans les deux configurations. Ou quelque-chose dans ce goût. J'en déduis que s'il existe une réponse rapide c'est que c'est impossible.

[Médiat]

D'après un invariant classique c'est possible.

[Juzo]

Je vous propose les réponses en spoiler :

@Missjenny

 Cliquez pour afficher

Ce premier raisonnement me paraît aller dans le bon sens, par contre je n'ai pas dit qu'il y avait une réponse rapide

@Mediat

 Cliquez pour afficher

Normalement ce n'est pas possible

[A voir en vidéo sur Futura]

[Médiat]

J'ai refait le calcul et je trouve bien que l'énergie est la même : donc possible

[Juzo]

J'ai refait le calcul et je trouve bien que l'énergie est la même : donc possible

Bonjour,

 Cliquez pour afficher

Pourtant l'article affirme et démontre de manière claire que ce problème n'a pas de solution. Je viens de le relire pour vérifier.

[Médiat]

Quel article ?

[MissJenny]

c'est quoi cette énergie? Il me semble de toutes façons qu'on ne peut pas utiliser un invariant pour montrer que la solution est possible.

[Médiat]

@MissJenny : ``Mais c'est impossible !'' Exemples d'utilisation d'invariants (univ-lyon1.fr) page 43

J'aurais dû écrire "pas impossible"

[Resartus]

Bonjour,
On peut remarquer que le mouvement de saut possède un inverse un "antisaut" qui consiste à sauter par dessus un trou pour faire apparaitre un pion
Deux configurations seront reliables s'il existe un chemin de sauts et d'antisauts pour passer de l'une à l'autre.
L'autre remarque est qu'on peut éliminer ou rajouter un triplet de 3 pions alignés avec une suite de tels mouvements
Les deux configurations décrites sont reliables, puisque on peut passer de la première à la seconde par suppression de paquets de 3 pions + deux sauts

Mais cela ne prouve pas qu'on puisse passer de l'une à l'autre avec seulement des sauts. Pour le prouver, il faudrait exhiber le chemin.
Si, comme l'écrit Juzo, c'est impossible, je ne vois pas bien comment démontrer cette impossibilité autrement que par force brute, ce qu'un ordinateur pourrait faire.

[Juzo]

Quel article ?

Article dans la revue Pour la Science de janvier 1995. Écrit par Ian Stewart, prof de mathématiques à l'Université de Warwick.

[Juzo]

Si, comme l'écrit Juzo, c'est impossible, je ne vois pas bien comment démontrer cette impossibilité autrement que par force brute, ce qu'un ordinateur pourrait faire.

Et pourtant...

[Médiat]

Pas d'accès sur le net ?

[Deedee81]

Salut,

Je n'arrive pas à remonter plus loin que 2000 sur le net (dans les archives PLS). Dommage

[Juzo]

J'ai seulement un scan de l'article.

[ArchoZaure]

Bonjour

On a pas mal de doc ici :
http://eternitygames.free.fr/Solitaire.html

Pour la faisabilité on a ça par exemple :
La règle de trois
http://eternitygames.free.fr/Solitai...e%20de%20trois

[Deedee81]

Ah grumpf, bloqué par le Service Public de Wallonie, sans doute à cause du mot "Games" !!!!!)

[Juzo]

On a pas mal de doc ici :

Il y a ce qu'il faut sur ce site

[Médiat]

Il y a plusieurs possibilités :

1. Je me suis trompé dans le calcul de l'invariant "énergie"
2. Cet invariant est non concluant dans ce cas (un invariant est concluant dans l'impossibilité, pas forcément dans la possibilité, et un autre invariant peut donner un résultat contraire)
3. L'image de départ et/ou celle de fin est fausse (c'est peu probable, je suppose que Juzo a juste scanné l'article)

[Juzo]

L'image vient effectivement du scan de l'article.

PS : le lien sur les exemples d'utilisation d'invariants ne fonctionne pas chez moi.

[Juzo]

Finalement j'ai réussi à télécharger le document

[Juzo]

Bonjour, indice :

La fonction Pagode est une fonction d'évaluation associant à chaque case du damier un nombre, de telle manière que lorsqu'on effectue des déplacements du solitaire, la somme des cases occupées par les pions ne peut que diminuer ou rester constante.

Si on prend trois cases successives (horizontalement ou verticalement) de valeurs , et , comme un pion peut passer par-dessus pour aller de en ou de en , cela signifie simplement qu'on a :

et

[Juzo]

Comment peut-on utiliser la fonction Pagode pour démonter qu'il est impossible de passer de la configuration 1 à la configuration 2 ?

(Désolé pour le flood, le prochain message sera la solution)

[Juzo]

Bonjour, voici la solution :

Cette fonction Pagode permet de résoudre le problème.

Fonction Pagode solution.png

La configuration 1 a un score de 4 (chaque branche vaut 1), la configuration 2 a un score de 6.
Or avec la fonction Pagode le score ne peut que baisser lorsqu'on effectue des déplacements.
Il est donc impossible de passer de la configuration 1 à la configuration 2.

N'hésitez pas à me dire si ce problème d'introduction était mal posé ou manquait d'intérêt.

[Juzo]

Pardon pardon j'avais promis de ne plus écrire de message!
@Mediat j'ai fait le calcul d'énergie avec le doc que vous avez donné, je trouve 0 dans la configuration 1 et 1 + dans la configuration 2 donc impossible.

Par contre ce sorti du chapeau, ça me titille . On peut le voir comme un nombre qui a une parité imaginaire ? je cherche à la rattacher à la notion de parité classique.

[MissJenny]

ah donc finalement ça n'était pas une fonction qui reste constante au cours du jeu mais une fonction qui décroît.

A mon avis le problème était intéressant. J'avoue que je n'aurais pas trouvé cette solution.

[Médiat]

@Juzo : je trouve (voir avec la racine cubique de l'unité) dans les 2 cas

[Juzo]

@Juzo : je trouve (voir avec la racine cubique de l'unité) dans les 2 cas

Aie, j'ai fait une erreur : j'ai pris une énergie de 0 pour un seul trou au milieu (d'après le doc, mais ici la croix n'a pas la même forme...) et j'ai enlevé 4 pions de la croix centrale ce qui ne changeait rien à l'énergie... On trouve bien dans les deux cas avec cet indiçage des diagonales, désolé pour le boulot en plus. Comme vous le disiez on peut conclure qu'il y a impossibilité quand l'énergie avant/après est différente, mais on ne peut rien conclure en cas d'égalité.

ah donc finalement ça n'était pas une fonction qui reste constante au cours du jeu mais une fonction qui décroît.

Merci pour ce retour. Dans le message #24 il y a une coquille : la fonction Pagode ne peut que décroitre ou rester constante, et pas uniquement "baisser" (comme expliqué plus haut).

L'énergie ne pouvait pas permettre de conclure ici. Par ailleurs la fonction Pagode a l'avantage d'utiliser une arithmétique classique, et de ne pas utiliser de nombre imaginaire...
Mais j'ai l'impression que la fonction Pagode est plus difficile à définir tandis que l'énergie a l'avantage d'être applicable directement pour n'importe quelle forme de plateau, et de permettre des calculs rapides.