Les solutions du solitaire peuvent être trouvées par ordinateur. « Indice » dans l’app Solitaire bille, comme les vérifications faites pour ce site, utilisent des programmes fondés sur la même idée. Voici leur principe, expliqué simplement.

Essayer tous les coups, l’un après l’autre

La méthode la plus directe consiste à choisir un coup possible et le jouer, puis à choisir encore un coup possible et à le jouer, et ainsi de suite. Quand on est bloqué, on revient d’un coup et l’on choisit un autre coup pas encore essayé.

  1. On choisit un coup possible sur le plateau actuel et on le joue.
  2. S’il ne reste qu’une bille, on a trouvé une solution.
  3. S’il n’y a plus de coup possible, on revient d’un coup et on en essaie un autre.
  4. Quand tous les coups ont été essayés, on revient encore d’un coup.

On appelle cette méthode la recherche en profondeur. C’est la même chose que ce qu’une personne fait avec « Annuler », mais répétée à une vitesse prodigieuse.

Ne pas examiner plusieurs fois la même position

Au solitaire, en jouant dans un ordre différent, on arrive souvent au même plateau. Sur le plateau anglais à 33 trous, après le 7e coup, il y a plus de 220 000 façons de jouer, mais seulement environ 22 000 positions différentes (Combien de solutions ?).

On mémorise donc les positions dont on a déjà vu qu’elles étaient sans issue, et quand on les rencontre à nouveau, on rebrousse chemin aussitôt. Cela réduit déjà beaucoup le travail.

Avec le programme utilisé pour ce site, la solution qui part du centre et finit au centre du plateau anglais à 33 trous a été trouvée instantanément (en moins de 0,1 seconde). Mais ce n’est pas toujours aussi rapide : en cherchant de la même façon à partir d’un plateau où l’on avait changé le 2e coup, il a fallu environ 9 secondes. Le temps varie beaucoup selon le coup par lequel on commence.

Abandonner sans regarder plus loin

Une autre astuce consiste à abandonner la recherche dès qu’on sait que, depuis cette position, on ne peut de toute façon pas atteindre l’objectif, sans examiner la suite. On appelle cela l’« élagage ».

L’app élague de deux façons.

  • La coloration en 3 couleurs : quand on colorie le plateau en diagonale avec 3 couleurs, la parité du nombre de billes change à chaque coup dans les 3 couleurs à la fois. Le calcul seul indique donc dans quels trous on peut encore finir à partir du plateau actuel (article sur la coloration en 3 couleurs).
  • La ligne et la colonne de la bille maîtresse : comme la bille maîtresse avance de deux trous à chaque fois, la parité de sa ligne et de sa colonne ne change pas (Garder la bille maîtresse en dernier).

S’il n’existe plus aucun trou qui remplisse les deux conditions, la bille maîtresse ne peut plus finir nulle part. On sait alors, sans même regarder la suite, que ce plateau est insoluble.

Dans « Indice » de l’app

« Indice » cherche, à partir du plateau actuel, un prochain coup qui mène à l’objectif, et l’illumine d’un cercle doré.

  • On connaît d’avance la réponse aux énigmes : un plateau « Énigmes » est créé en sautant à rebours, donc on connaît la réponse trouvée à la création (Comment on crée des énigmes toujours solubles). Comme on a retenu que les positions sur ce chemin sont solubles, on répond tout de suite. Même sur une position hors du chemin, si la recherche rejoint le chemin de la réponse, elle s’arrête là.
  • Une limite à la recherche : un indice examine au plus 1,5 million de positions ou 3 secondes. Sur un grand plateau, il arrive qu’on n’ait pas de réponse avant.
  • Dire de combien de coups revenir : quand le plateau actuel ne peut plus atteindre l’objectif, ou quand on n’a pas trouvé avant la limite, l’app examine les positions où l’on peut revenir avec « Annuler » et dit de combien de coups revenir, par exemple « Reviens de 3 pour sauver ». Comme elle cherche en divisant l’intervalle en deux à chaque fois, elle trouve vite même quand il y a beaucoup de coups.

Conseils pour résoudre soi-même

Les astuces de l’ordinateur servent aussi à une personne.

  • Retenir les formes sans issue : une forme qui a échoué une fois échoue encore si on y arrive dans un autre ordre.
  • Raisonner depuis l’arrivée : les trous où l’on peut finir sont connus dès le départ. Si l’on choisit d’abord le trou visé, il est plus facile de choisir ses coups (Finir au centre).
  • Revenir et essayer : comme dans la recherche en profondeur, revenir un peu en arrière quand on hésite et essayer un autre coup est la bonne méthode.