Baguenaudier

D’après sujet 25-NSIJ1PO1

Le jeu du baguenaudier est un jeu de casse-tête constitué d’une réglette comportant n cases, numérotées de 1 à n.

Chaque case peut être soit vide, soit contenir un pion.

« Jouer » une case consiste à placer un pion dans la case (remplir) si elle est vide ou enlever un pion (vider) si elle est remplie.

Initialement, toutes les cases sont vides.

Le but du jeu est de remplir toutes les cases du baguenaudier en suivant les règles suivantes :

• on ne peut jouer qu’une case à la fois ;
• chaque case ne peut contenir qu’un pion ;
• on peut toujours jouer la case 1 ;
• si le baguenaudier n’est ni vide ni rempli, on peut aussi jouer la case qui suit la première case remplie ;
• aucune autre case ne peut être jouée.

Exemple de situation avec un baguenaudier de 5 cases :

Dans cette situation, on peut poser un pion dans la case 1 ou enlever le pion de la case 4 mais on ne peut pas jouer les cases 2, 3 et 5.

Résolution

Il est possible de résoudre automatiquement le jeu du baguenaudier, en utilisant des fonctions récursives nommées vider et remplir.

Ces deux fonctions prennent en paramètre un entier n correspondant au nombre de cases du jeu.

• La fonction vider vide un baguenaudier de n cases initialement remplies.
• La fonction remplir remplit un baguenaudier de n cases initialement vides.

Les actions opérées par le joueur se font case par case à l’aide de deux fonctions remplir_case et vider_case qui prennent en paramètre un entier i correspondant à l’indice  de la case à remplir ou vider.

Exemple de résolution d’un jeu à 4 cases :