Y a-t-il une configuration de Free Cell qui ne peut être résolue ?

Question

Lorsque j'ai du temps libre par petites durées, je joue souvent à Free Cell sur mon téléphone. L'application que j'utilise permet un nombre illimité d'annulations, et grâce à cela, j'ai actuellement une série de 603 victoires, avec 655 victoires totales et 10 pertes totales.

Comme le démontrent ces statistiques, mes 10 défaites ont eu lieu au cours de mes 52 premiers matchs. Avant d'utiliser cette application, je n'avais joué que très rarement à Free Cell.

Comme mes statistiques approchent un taux de perte de 1%, je me pose des questions : Étant donné la possibilité illimitée de défaire vos mouvements, y a-t-il une affaire initiale de Free Cell qui soit impossible à résoudre ?

Une preuve dans un sens ou dans l'autre serait idéale (bien que j'admette que je doute d'être capable de comprendre une telle preuve), bien qu'une source faisant autorité serait une bonne alternative.

Answer 1

Il n'est pas difficile de prouver qu'il existe un début d'insoluble. Il suffit d'imaginer un départ où les seuls premiers mouvements possibles seraient de déplacer des cartes vers les cellules supplémentaires. Dans certaines versions, -1 et -2 en sont des exemples, bien que la seule façon de les jouer soit de choisir cette graine.

Si l'on ne compte que les configurations qui peuvent exister en jeu normal, la graine 11982 de la version Windows en est un exemple :

Parmi les 32000 parties originales de Freecell, 11982 est la seule pour laquelle aucune solution légitime n'a été trouvée. Depuis lors, plusieurs ordinateurs et joueurs n'ont pas réussi à trouver une solution - au point que toutes les combinaisons possibles de mouvements ont été essayées et ont échoué.