« Peut-on gagner toutes les donnes du FreeCell ? » « Est-il vrai qu’il y a des donnes impossibles ? » Beaucoup de gens se le demandent. La réponse : presque toutes les donnes se gagnent, mais de très rares donnes sont impossibles. Voici ce qu’on en dit, avec les résultats de vrais calculs.

Les 32 000 donnes de Windows, et la n° 11982

L’ancien FreeCell de Windows proposait des donnes numérotées de 1 à 32 000. On raconte bien souvent qu’en les résolvant à de nombreux joueurs sur Internet, seule la n° 11982 s’est révélée impossible.

Pour cette page, nous avons écrit un programme qui cherche des solutions avec les mêmes règles que l’app FreeCell, et nous lui avons fait résoudre toutes les donnes de 1 à 32 000, générées à partir de leur numéro par le calcul bien connu.

RésultatNombre de donnes
Solution trouvée31 999
Impossible, vérifié1

La seule donne dont nous avons vérifié qu’elle est impossible est la n° 11982. Pour les 31 999 autres, une solution a été trouvée. C’est bien ce que raconte la légende.

Le schéma ci-dessous montre cette donne n° 11982.

AAAAA♥♥3♦♦K♦♦J♣♣6♣♣J♦♦K♣♣A♠♠3♥♥6♥♥5♦♦2♣♣7♦♦8♦♦4♥♥Q♠♠5♠♠5♣♣10♥♥8♥♥2♠♠A♣♣Q♣♣4♦♦8♣♣Q♥♥9♣♣3♠♠2♦♦8♠♠9♥♥9♦♦6♦♦2♥♥6♠♠7♥♥J♥♥10♦♦10♣♣Q♦♦10♠♠A♦♦9♠♠K♥♥4♠♠4♣♣J♠♠K♠♠3♣♣7♣♣7♠♠5♥♥

Trois des quatre as (cœur, pique, trèfle) sont tout au fond des colonnes 1, 2 et 4. Chacun de ces trois as est couvert par 6 cartes. L’as de carreau est l’avant-dernière carte de la colonne 7, avec 4 cartes au-dessus.

Comment a-t-on vérifié qu’elle est impossible ?

Pour vérifier qu’une donne est impossible, il n’y a qu’un moyen : explorer toutes les positions qu’on peut atteindre à partir de cette donne. Avec le programme de cette page, la donne n° 11982 donne environ 95 000 positions atteignables, et aucune ne permet de monter les 52 cartes aux fondations. Dans l’app FreeCell, on peut aussi reprendre une carte de la fondation, et cette exploration en tient compte (Comment un ordinateur résout-il le FreeCell ?).

Les donnes de l’app FreeCell

L’app FreeCell n’a pas de numéros de donne. À chaque « Nouvelle partie », elle mélange les 52 cartes au hasard.

L’auteur a fait résoudre par ordinateur 100 000 donnes créées au hasard comme dans l’app, puis a rejoué chaque solution trouvée jusqu’au bout avec le même moteur de jeu que l’app. Résultat : les 100 000 donnes avaient une solution.

Pourquoi dire « presque »

On ne peut pourtant pas affirmer que « toutes les donnes sont gagnables ».

Comme aucune des 100 000 donnes vérifiées n’était impossible, on peut estimer que la proportion de donnes impossibles est, au plus, inférieure à environ 1 sur 27 000 (c’est la limite supérieure, avec une confiance de 95 %, calculée d’après les résultats des 100 000 donnes par une méthode statistique classique). En jouant normalement, on ne rencontrera presque jamais une donne impossible.

Si vous pensez que la donne est impossible

Quand vous êtes bloqué, c’est presque toujours à cause de l’ordre de vos coups, et non de la donne. Essayez un autre ordre avec « Annuler » ou « Rejouer » (Quand on est bloqué). La façon de réfléchir est regroupée dans Les astuces du FreeCell et Stratégie et méthode gagnante.