Dans le mode « Énigmes » de l’app Solitaire bille, un plateau de forme différente est créé à chaque « Nouvelle partie ». Pourtant, chaque plateau a toujours une solution. Cet article explique le principe.

Créer au hasard ne garantit pas une solution

Si l’on décide au hasard de la forme des trous et de la position des billes, on obtient beaucoup de plateaux insolubles. Pour savoir si un plateau est soluble, il faut examiner tous les coups, ce qui prend du temps quand il y a beaucoup de billes.

L’app utilise donc une méthode qui crée l’énigme à l’envers, depuis la réponse.

Sauter à rebours

Un coup de solitaire consiste à faire sauter une bille par-dessus la bille voisine jusqu’au trou vide, et à retirer la bille survolée. Si on le joue à rebours, cela donne :

une bille revient 2 trous plus loin dans un trou vide, et l’on pose une bille dans le trou vide du milieu

À chaque coup à rebours, il y a une bille de plus.

On part de la bille maîtresse seule

On enchaîne des coups à rebours à partir d’un plateau où il ne reste que la bille maîtresse (c’est-à-dire un plateau réussi). Voyons un petit exemple.

D’abord, un plateau avec seulement la bille maîtresse.

1er coup : on fait revenir la bille maîtresse 2 trous plus haut, et l’on pose une bille entre les deux.

2e coup : on fait revenir la bille posée 2 trous plus à gauche, et l’on pose une bille entre les deux.

3e coup : on fait revenir la bille maîtresse 2 trous plus à droite, et l’on pose une bille entre les deux.

On a maintenant une énigme à 4 billes.

Les coups à rebours sont directement la réponse

Si l’on rejoue les coups créés du dernier au premier, dans le sens normal, on obtient directement la réponse. Dans l’exemple, en ne gardant comme trous du plateau que les trous utilisés, on résout l’énigme ainsi.

  1. Coup 1 e1→c1
  2. Coup 2 a2→c2
  3. Coup 3 c1→c3
  4. Après le coup 3 Billes restantes : 1

Comme la suite de coups à rebours part d’un plateau déjà réussi, la rejouer dans le sens normal laisse forcément la bille maîtresse seule. C’est pourquoi chaque énigme a la garantie d’avoir au moins une solution.

Les améliorations de l’app

L’app ajoute quelques astuces à cette méthode.

  • Réutiliser les trous : en choisissant les coups à rebours, on favorise ceux qui réutilisent un trou déjà utilisé. Les coups s’entremêlent, et l’énigme risque moins de n’être qu’une simple ligne droite.
  • Régler la forme du plateau : pour la moitié des plateaux obtenus, on ajoute des trous pour que la forme soit symétrique gauche-droite. Pour les autres, on ajoute 1 ou 2 trous vides au bord pour changer la forme. Ajouter des trous vides ne change pas la réponse d’origine, qui reste jouable : l’énigme reste soluble.
  • Même énigme avec la même graine : l’énigme est créée à partir d’un nombre appelé « graine ». Avec la même graine et la même difficulté, on obtient la même énigme sur iPhone et sur Android.

On mesure la difficulté, et on recommence si elle ne convient pas

Une énigme créée à rebours a toujours une réponse. Mais cela ne suffit pas : elle peut être trop facile ou trop difficile.

L’app examine donc chaque énigme créée en regardant, le long de la solution, combien de coups, une fois joués, empêchent de garder la bille maîtresse (les coups pièges). Elle refait l’énigme jusqu’à 24 fois, jusqu’à ce que la proportion de coups pièges entre dans la plage de chaque niveau de ★1 à ★5 (les plages sont dans l’article sur les difficultés).

Même pour une énigme ★5 Grand maître (27 à 32 billes), la création prend en moyenne environ 0,6 seconde sur le Mac utilisé pour le développement. De plus, 3 énigmes sont préparées à l’avance pour chaque difficulté et recréées en arrière-plan à mesure qu’on les utilise : le joueur n’attend presque jamais.

La réponse n’est pas forcément unique

La suite de coups créée à rebours n’est qu’une des réponses. Un même plateau a souvent plusieurs autres réponses. Les plateaux « Entraînement bille maîtresse » de la page pour jouer sont créés selon le même principe, et celui à 16 billes a plus de 3 millions de solutions (Combien de solutions ?).

« Indice » dans l’app se souvient de la réponse trouvée à la création : tant que vous êtes sur ce chemin, elle peut vous donner tout de suite le prochain coup. Si vous vous en écartez, un programme de recherche cherche un autre chemin (Résoudre avec l’ordinateur).