Solutions

Après quelques jours de tentatives infructueuses, j'ai décidé d'écrire un programme qui cherche les solutions.

Stratégie

Force brute : le programme cherche toutes les solutions possibles. Il considère les positions successives du trou (la case qui n'a pas de bille). En effet, une partie est entièrement déterminée par la liste des positions du trou.

Une fonction récursive teste les mouvements du trou vers les différentes cases atteignables. Si un mouvement est autorisé par les règles, il est effectué. L'état du plateu est alors affiché, ainsi que la liste des mouvements du trou et le score (le nombre de billes qui sont du bon côté).

Lorsque le programme trouve une solution (score = 16), la suite des positions du trou est écrite dans un fichier nommé solutions.

Les cases sont numérotées de la manière suivante : 

      02          10
   01    05    09    13
00    04    08    12    16
   03    07    11    15
      06          14

Exemples de solutions

Le programme trouve rapidement des milliers de solutions. Voilà un exemple :
8-9-7-6-8-11-12-9-7-4-3-6-8-11-13-12-9-7-4-1-0-3-6-8-10-9-7-8-
5-11-14-15-16-13-12-15-9-8-2-1-7-4-5-11-8-14-11-12-9-7-8-2-5-11-8

Visualisation des solutions

Le script playSol.pl, écrit en perl, permet de visualiser les solutions contenues dans le fichier solutions. Les parties sont jouées à l'écran à raison d'un coup par seconde.

suiteAnalyse des 10'000 premières solutions.

Code source