Le Solitaire - Nouveau lycée de Vincennes (Vincennes)

Le jeu de solitaire se joue (tout seul évidemment) sur un plateau où sont tracées des lignes sur lesquelles se trouvent des trous. Tous les trous sont occupés par des billes. On enlève l’une des billes, puis le jeu commence : chaque coup consiste à faire sauter une bille au-dessus de l’une de ses voisines (en suivant une ligne) pour atterrir dans la case suivante (qui doit être libre), puis à enlever la bille qui a été survolée. Le jeu est gagné quand il ne reste qu’une bille.
Dans un premier temps, on s’intéressera à différentes formes de plateaux (par exemple, des rectangles quadrillés, ou des triangles, ou les plateaux classiques de solitaire) et on se demandera lesquels de ces jeux peuvent être résolus, si l’on dispose d’un algorithme explicite pour le résoudre, et aussi si cela dépend de la position de la bille retirée au début du jeu.
Dans un second temps, on pourra étudier la variante suivante : le plateau est une quadrillage infini, et toutes les positions de la moitié inférieure du plateau sont occupées par des billes. On cherche alors à faire monter des billes le plus haut possible sur ce plateau, en respectant les règles précédentes. Votre défi : monter le plus haut possible !