Nous souhaitons créer un environnement permettant de jouer au puissance 4.

• Le jeu se joue sur une grille de 6 lignes et 7 colonnes.
• Chaque joueur a une couleur de jeton – jaune et rouge en général.
• Chaque joueur, a son tour, insère un jeton dans la colonne de son choix, si bien sûr elle n'est pas déjà pleine. Le jeton tombe dans la case libre la plus bas de la colonne.
• Un joueur gagne quand il crée un alignement de 4 de ses jetons, horizontalement, verticalement ou en diagonale.
• Si la grille est pleine et qu'il n'y a toujours aucun alignement, c'est un match nul.

Nous devons distinguer deux aspects différents de notre programme :

• D'un côté, nous avons besoin d'un ensemble de commande qui permettent l'évolution du jeu : insérer un jeton dans une colonne, décider à quelle ligne tombe le jeton, rechercher un alignement, etc. C'est la bibliothèque de fonction.
• De l'autre il nous faut dérouler une partie. Demander au premier joueur de choisir une colonne, puis passer au second joueur, etc ; ou bien on pourrait faire jouer l'humain contre la machine ; ou encore faire jouer la machine contre la machine. Il s'agit du programme principal qui utilise les fonctions de la bibliothèque.

On va commencer par produire toute une liste de fonctions utiles. Chacune de ces fonctions réalisent un petit aspect du jeu. Ensuite, on pourra réaliser le programme principal.

Le jeu normal se joue sur 7 colonnes, 6 lignes et avec des alignements de 4. Nous allons donc trouver dans notre programme des 7, des 6 et des 4 à de nombreux endroits.

Supposons que l'on veuille essayer un puissance 4 sur une grille de 11×8. Cela ne devrait pas poser de difficultés pour un ordinateur. Pourtant, si nous avons écrit 7 et 6 un peu partout dans le programme, il nous faudra remplacer tous les 7 par 11 et tous les 6 par 8. C'est pénible…

Au lieu de cela on commence le programme en définissant des constantes :

"""
module fonctionspuissance4
"""

COLS = 7   # Nombre de colonnes de la grille
LIGNES = 6 # Nombre de lignes de la grille
TO_WIN = 4 # Nombre de jetons à aligner pour gagner

Le programme a besoin de savoir à chaque instant l'état de la grille : que contient telle ou telle case ?

Il y a plusieurs possibilité.

• Il serait naturel d'utiliser un tableau à deux dimensions : 7 lignes et 6 colonnes.
• On peut aussi utiliser un tableau à 1 dimension contenant 7×6 cases.

Je préconise la seconde solution. Le tableau contiendra donc LIGNES * COLS cases. La case pour la ligne lig et la colonne col sera située à la position lig * COLS + col. Les numéros de lignes et colonnes commencent à 0, la ligne 0 est en haut.

On décide aussi que

• une case vide contient le numéro 0,
• une case contenant le jeton du joueur 1 contient 1,
• une case contenant le jeton du joueur 2 contient 2,
• et ainsi de suite – rien n'empêche d'envisager un jeu à plus de 2 joueurs !

Voici un exemple. Ici le joueur 1 a les jeton jaunes et le joueur 2 a les jetons rouges.

# tableau correspondant
[0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0,
 0, 0, 1, 0, 0, 0, 0,
 0, 0, 2, 1, 2, 0, 0,
 0, 1, 2, 2, 1, 0, 0,
 2, 1, 1, 1, 2, 2, 0]

Bien que j'ai noté ce tableau sur plusieurs lignes, il s'agit bien d'un tableau à une dimension puisqu'il n'y a qu'une paire de crochets.

def make_empty_grid():
    """
    Renvoie un tableau de LIGNES * COLS cases et ne contenant que des 0
    """
    # à vous de compléter

def read(grid, lig, col):
    """
    grid: tableau de LIGNES * COLS éléments
    lig: entier dans [0;LIGNES[, indice de ligne
    col: entier dans [0;COLS[, indice de colonne
    Renvoie le contenu de grid correspondant à la ligne lig et colonne col
    """
    assert 0 <= lig < LIGNES
    assert 0 <= col < COLS
    assert len(grid) == LIGNES * COLS
    return # Complétez !

Il pourra être utile de donner une version lisible du contenu de la grille. Je propose la solution suivante.

SYMBOLS = " OX" # symboles pour les différents joueurs.
# SYMBOLS[0] correspond à une case vide.

def display(grid):
    """
    grid: tableau de LIGNES * COLS éléments
    affiche la grille en mode texte dans la console.
    """
    # création d'une grille avec les symboles au lieu des numéros
    symb_grid = [SYMBOLS[joueur] for joueur in grid]
    # création d'une grille de ligne
    symb_lignes = ["|"+"|".join(symb_grid[lig*COLS:(lig+1)*COLS])+"|" for lig in range(LIGNES)]
    return "\n".join(symb_lignes)

C'est un peu compliqué. Quelques détails pour les plus curieux :

• symb_grid = [SYMBOLS[joueur] for joueur in grid] utilise un tableau en compréhension : On crée directement un tableau dont les éléments sont obtenus par exécution de la boucle.
• symb_grid[lig*COLS:(lig+1)*COLS] permet d'extraire un tronçon correspondant à une ligne lig donnée,
• "|".join(symb_grid[lig*COLS:(lig+1)*COLS]) permet de coller les éléments de ce tronçon avec un trait de séparation de colonne,
• "|"+"|".join(symb_grid[lig*COLS:(lig+1)*COLS])+"|" permet d'ajouter des traits de colonnes au début et à la fin,
• [... for lig in range(LIGNES)] permet de faire cela pour toutes les lignes et de mettre l'ensemble des résultats dans un tableau,
• "\n".join(symb_lignes) permet de coller les lignes obtenus par un symbole de retour chariot – retour à la ligne – que l'on note "\n".

Une colonne si la case du haut de cette colonne est occupée. Pour une colonne col il nous suffit de lire le contenu de cette colonne et de la ligne 0 et de voir si le contenu est occupé.

def col_is_full(grid, col):
    """
    grid: tableau de LIGNES * COLS éléments
    col: indice de la colonne
    renvoie True si la colonne est pleine, False sinon
    """
    # à vous...

Il faut vérifier chaque colonne. Si au moins une n'est pas pleine, c'est que la grille n'est pas pleine.

def grid_is_full(grid):
    """
    grid: tableau de LIGNES * COLS éléments
    renvoie True si la grille est pleine, False sinon
    """
    # à vous...

Ajoute un jeton du joueur donné dans la plus haute case libre de la colonne.

def insert(grid, col, player):
    """
    grid: tableau de LIGNES * COLS éléments
    col: indice de la colonne
    player: numéro du joueur
    """
    assert not col_is_full(grid, col)
    # À vous !

Cette partie est plus difficile. L'humain reconnaît d'un coup d’œil la présence ou l'absence d'alignement. Je vous propose l'approche suivante :

• On choisit une orientation – diagonale ↘, diagonale ↗, verticale, horizontale
• On choisit un point de départ, par exemple le coin supérieur gauche
• On parcours la grille depuis ce point de départ dans la direction donnée et on compte les symboles rencontrés. Pour cela, on mémorise le contenu de la case précédente et quand la nouvelle case est identique on ajoute 1 à un compteur. Comme on ne veut pas compter les cases vides, on n'ajoute 1 que si la nouvelle case n'est pas une case vide.
• Quand on en rencontre une quantité suffisante pour faire un alignement on répond que la fonction a trouvé un alignement.
• Si on atteint un bord sans trouver d'alignement, la fonction répond qu'elle n'a pas trouvé d'alignement.

Voici un algorithme possible

ENTRÉES
  grille
  pas: déplacement à faire d'un case à l'autre
  départ: position de départ
DÉBUT
  soit position en cours définie par la position de départ
  soit 0 le contenu en cours
  soit 0 la valeur du compteur
  TANT QUE position en cours à l'intérieur de la grille RÉPÉTER
    soit j le contenu de la grille à la position en cours
    SI j == 0 ALORS
      mettre compteur à 0 et contenu en cours à 0
    SINON SI j == contenu en cours ALORS
      augmenter le compteur de 1
    SINON
      contenu en cours devient égal à j
      Le compteur passe à 1
    FIN
    SI compteur >= quantité nécessaire pour gagner ALORS
      RENVOYER VRAI
    FIN
    changer la position courante selon le pas
  FIN
  RENVOYER FAUX
FIN

Traduisez cet algorithme en fonction.

def line_has_victory(grid, step, start):
    """
    grid: grille de jeu
    step: paire (step_lig,step_col) indiquant le déplacement d'une case à la suivante
    start: paire (start_lig, start_col) indiquant la position de départ
    renvoie True si un alignement gagnant a été trouvé, False sinon
    """
    # À vous !

Exemple d'utilisation :

• line_has_victory(grid, (1,1), (0,0)) recherche une victoire dans la diagonale ↘ partant du coin supérieur droit,
• line_has_victory(grid, (1,1), (0,1)) recherche une victoire dans la diagonale ↘ partant de la deuxième case de la première ligne,
• line_has_victory(grid, (-1,1), (0,3)) recherche une victoire dans la diagonale ↙ partant de la quatrième case de la première ligne,
• line_has_victory(grid, (0,1), (0,3)) recherche une victoire dans la colonne partant de la quatrième case de la première ligne,
• line_has_victory(grid, (1,0), (2,0)) recherche une victoire dans la troisième ligne.

Et maintenant vous pouvez envisager une fonction qui parcours toutes les lignes possibles à la recherche d'une victoire.

def grid_has_victory(grid):
    """
    grid: grille de jeu
    renvoie True si un alignement gagnant a été trouvé, False sinon
    """
    # À vous !

À placer dans un fichier fonctionspuissance4.py.

"""
module fonctionspuissance4
"""

COLS = 7   # Nombre de colonnes de la grille
LIGNES = 6 # Nombre de lignes de la grille
TO_WIN = 4 # Nombre de jetons à aligner pour gagner

def make_empty_grid():
    """
    Renvoie un tableau de LIGNES * COLS cases et ne contenant que des 0
    """
    # à vous de compléter
    
def read(grid, lig, col):
    """
    grid: tableau de LIGNES * COLS éléments
    lig: entier dans [0;LIGNES[, indice de ligne
    col: entier dans [0;COLS[, indice de colonne
    Renvoie le contenu de grid correspondant à la ligne lig et colonne col
    """
    assert 0 <= lig < LIGNES
    assert 0 <= col < COLS
    assert len(grid) == LIGNES * COLS
    return # Complétez !

SYMBOLS = " OX" # symboles pour les différents joueurs.
# SYMBOLS[0] correspond à une case vide.

def display(grid):
    """
    grid: tableau de LIGNES * COLS éléments
    affiche la grille en mode texte dans la console.
    """
    # création d'une grille avec les symboles au lieu des numéros
    symb_grid = [SYMBOLS[joueur] for joueur in grid]
    # création d'une grille de ligne
    symb_lignes = ["|"+"|".join(symb_grid[lig*COLS:(lig+1)*COLS])+"|" for lig in range(LIGNES)]
    return "\n".join(symb_lignes)

def col_is_full(grid, col):
    """
    grid: tableau de LIGNES * COLS éléments
    col: indice de la colonne
    renvoie True si la colonne est pleine, False sinon
    """
    # à vous...

def grid_is_full(grid):
    """
    grid: tableau de LIGNES * COLS éléments
    renvoie True si la grille est pleine, False sinon
    """
    # à vous...

def insert(grid, col, player):
    """
    grid: tableau de LIGNES * COLS éléments
    col: indice de la colonne
    player: numéro du joueur
    """
    assert not col_is_full(grid, col)
    # À vous !

def line_has_victory(grid, step, start):
    """
    grid: grille de jeu
    step: paire (step_lig,step_col) indiquant le déplacement d'une case à la suivante
    start: paire (start_lig, start_col) indiquant la position de départ
    renvoie True si un alignement gagnant a été trouvé, False sinon
    """
    # À vous !

def grid_has_victory(grid):
    """
    grid: grille de jeu
    renvoie True si un alignement gagnant a été trouvé, False sinon
    """
    # À vous !

Il faut importer les fonctions définies précédemment.

"""
module: main
"""

from fonctionspuissance4 import *

Ensuite le jeu suit l'algorithme suivant :

DÉBUT
  créer une grille vide
  afficher la grille
  joueur en cours est 1
  partie_finie est faux
  TANT QUE partie finie est faux RÉPÉTER
    demander au joueur en quelle colonne il souhaite jouer
    jouer le coup pour le joueur en cours
    afficher la grille
    SI la grille contient une victoire ALORS
      partie_finie passe à vrai
      afficher un message indiquant la victoire du joueur
    SINON SI la grille est pleine ALORS
      partie_finie passe à vrai
      afficher un message indiquant le match nul
    FIN
  FIN
FIN

À vous de compléter le fichier main.py