vendredi 1 juillet 2011

Permutation heureuse

Partager


Comme on n'est jamais assez prêt pour le centre d'accueil, je fais quotidiennement au moins une partie de Freecell que je recommence tant et aussi longtemps que je ne la réussis pas. Je peux même affirmer que si une partie se fait en moins de 3 minutes, la suite de la journée ira bien. En plus de deux essais, il vaut mieux rester couché. Digne disciple de Girolamo !

Au départ, dans Freecell, les 52 cartes sont distribuées sur 8 colonnes (4 colonnes de 7 cartes et 4 colonnes de 6 cartes). Comme on ne peut pas piger n'importe où dans les colonnes, l'ordre des cartes à l'intérieur d'une colonne est important. L'ordre des colonnes ne l'est pas (4!*4! permutations de ces colonnes). On peut aussi interchanger les coeurs-carreaux (2 possibilités (on le fait ou on ne le fait pas)) et les trèfles-piques (2 possibilités itou) sans vraiment changer le jeu. Et on peut ou pas changer les cartes rouges en cartes noires et les cartes noires en cartes rouges (2 possibilités).

On a donc 52 ! / (4! * 4! * 2 * 2 * 2) = 17 503 944 264 527 751 426 141 631 262 240 400 819 290 257 257 136 128 000 000 000 000 jeux différents.

À une partie par seconde, il y a de quoi jouer pendant plus de 554 septendécillons d'années. C'est ce qui s'appelle se préparer à l'éternité.

Est-il vrai que toutes les parties sont résolubles ?

Micro$oft aurait dans les 32 000 parties différentes offertes dans sa version 3.1 une partie célèbre, la 11 982 qui ne pourrait pas être réussie. Maintenant qu'elle offre plus d'un million de parties différentes, il y en aurait 8 qui ne seraient pas résolubles.



Tout ça pour vous dire que...

Hier, j'ai attrapé cette partie :





Inutile de vous dire que j'ai passé une très très belle journée.

4 commentaires:

Stéphane Laborde a dit...

Y-a-t-il un test mathématique simple qui permet d'affirmer que telle ou telle configuration est résoluble, ou faut-il passer par un algithme alpha-beta brutal ?

Prof Malgré Tout a dit...

No way...

Sonia Geffrier a dit...

Tu aurais mieux fait de jouer au Loto ce jour-là !

Missmath a dit...

Ma première réaction a été : "Il doit y avoir un bogue". En effet, j'aurais dû jouer au loto sur ce coup-là !

Stéphane, il existe des algorithmes permettant d'accélérer la résolution d'un jeu, mais pour démontrer qu'une configuration n'a pas de solution, hélas, il n'y a que l'approche brutale. C'est sans doute ce qui explique pourquoi il a fallu attendre des mois avant la confirmation que le jeu 11982 n'avait pas de solution.