Exercice 3 - Question 5 : Récursivité · Bac Numérique et Sciences Informatiques Amérique du Sud 2023 (jour 2)

Exercice 3 (4 points)

Au jeu de go, les deux adversaires placent à tour de rôle des pierres, respectivement noires et blanches, sur les intersections d'un plateau quadrillé appelé goban. Une partie se joue généralement sur un goban de $19 \times 19$ intersections, mais des gobans de $13 \times 13$ et $9 \times 9$ peuvent être utilisés pour s'entraîner.

On a reproduit ci-dessous un début de partie sur un goban de $19 \times 19$.

On s'intéresse dans cet exercice à l'une des règles du jeu de go, dite d'encerclement, pour laquelle on doit compter ce qui s'appelle les libertés d'une pierre ou d'une chaîne de pierres.

Les libertés d'une pierre sont les intersections libres autour d'elle selon les quatre directions cardinales (nord, sud, est et ouest). Dans chacun des exemples suivants, on donne le nombre de libertés de chacune des pierres noires.

On appelle chaîne de pierres une suite de pierres liées entre elles selon les directions cardinales. Le nombre de libertés d'une chaîne de pierres s'obtient alors en comptant, sans répétition, les libertés de chacune des pierres qui la composent.

Les exemples ci-dessous mettent en lumière cette règle sur une chaîne de pierres.

On se propose de représenter un état du jeu sur un goban $n \times n$ (où $n$ peut valoir uniquement 9, 13 ou 19) par une liste de $n$ listes toutes de longueur $n$. Chaque intersection sera définie par un numéro de ligne $i$ et un numéro de colonne $j$.

L'intersection en haut à gauche (nord - ouest) est repérée par les indices $i = 0$ et $j = 0$ tandis que celle en bas à gauche (sud - ouest) est repérée par les indices $i = n - 1$ et $j = 0$.

Pour chaque intersection, la présence d'une pierre noire est codée par le nombre 1,

celle d'une pierre blanche par le nombre -1,

l'absence de pierre par le nombre 0.

Par exemple, voici un goban de $9 \times 9$ et sa représentation par la liste goban.

goban = [[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0],

[0, 0,-1, 0,-1, 1, 0, 0, 0],

[0, 0, 0, 0,-1, 0, 1, 1, 0],

[0, 0,-1, 0, 1, 0, 0, 0, 0],

[0, 0, 0, 0, 0,-1, 0, 0, 0],

[0, 0, 1, 1, 0,-1, 0, 0, 0],

[0, 0, 0, 0, 1, 0, 0, 0, 0],

[0, 0, 0, 0, 0, 0, 0, 0, 0]

] Pour la suite de l'exercice, on aura besoin de la fonction est_valide(i, j, n) définie par le code suivant.

def est_valide(i, j, n):

return 0<=i<n and 0<=j<n Cette fonction renvoie la valeur True si les indices i et j passés en paramètres représentent une position valide sur un goban $n \times n$, et False sinon.

Cette fonction pourra être utilisée dans la suite de cet exercice.

5. On souhaite maintenant écrire une fonction cherche_chaine qui construit, étant donnée la position (pi, pj) d'une pierre, la chaine de pierres qui contient cette pierre. Pour cela, on examine récursivement les pierres voisines de même couleur et on ajoute leurs positions à une liste chaine initialement vide.

Sur votre copie, recopier et compléter les lignes 48 et 49 de cette fonction.

42 def cherche_chaine(go, pi, pj, chaine):

43 n = len(go)

44 chaine.append((pi, pj))

45 couleur = go[pi][pj]

46 for i, j in [(pi+1, pj), (pi-1, pj),

47 (pi, pj+1), (pi, pj-1)]:

48 if est_valide(i, j, n) and... and...:

49 cherche_chaine(...)

50 return chaine

Par exemple, pour le goban ci-contre, l'appel cherche_chaine(goban, 3, 1, []) renvoie la liste [(3, 1), (4, 1), (2, 1), (2, 2), (2, 3)].