Aller au contenu

E07 - Échec et mat⚓︎

Le problème

Échec et mat

Indices⚓︎

  • Par tradition, on note \((i, j)\) les coordonnées dans une grille (ou une matrice), avec \(i\) l'indice de ligne, et \(j\) celui de colonne. Dans l'exemple précédent, il y a deux reines, une en \((1, 1)\), l'autre en \((4, 3)\). La case \((0, 0)\) correspond au coin supérieur gauche. Si on tourne la tête de \(90°\), cela correspond à abscisse et ordonnée.
  • On pourra créer une fonction est_valide(i, j) qui renvoie un booléen : si la case de coordonnées \((i, j)\) est bien dans l'échiquier.
  • On pourra créer une fonction marque(i_0, j_0) qui modifie une grille en marquant les cases menacées par une reine placée en \((i_0, j_0)\).
  • Ce problème est plus simple que le précédent !

Solution⚓︎

Une approche⚓︎

🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2013/semifinal/echec_et_mat
"""

REINE = 'X'
LIBRE = '.'
DANGER = 'o'

def est_valide(i: int, j: int) -> bool:
    """Renvoie un booléen : (i, j) est-il dans la grille 8×8?
    Les coordonnées vont de 0 à 7.

    >>> est_valide(2, 5)
    True

    >>> est_valide(5, 8)
    False

    >>> est_valide(-2, 5)
    False

    """
    return (0 <= i < 8) and (0 <= j < 8)

def est_reine(i: int, j: int) -> bool:
    return grille[i][j] == REINE

def est_libre(i: int, j: int) -> bool:
    return grille[i][j] == LIBRE

def marque_case(i: int, j: int):
    """Modifie la grille en (i, j),
    uniquement si elle est libre.
    """
    if est_libre(i, j):
        grille[i][j] = DANGER

def marque_grille(i_0: int, j_0: int) -> None:
    """Modifie la grille, en marquant les cases menacées
    par une reine placée en (i_0, j_0).
    """
    # on marque la colonne j_0
    for i in range(8):
        marque_case(i, j_0)

    # on marque la ligne i_0
    for j in range(8):
        marque_case(i_0, j)

    # on marque une diagonale
    for k in range(-7, 8):
        i = i_0 + k
        j = j_0 + k
        if est_valide(i, j):
            marque_case(i, j)

    # on marque l'autre diagonale
    for k in range(-7, 8):
        i = i_0 + k
        j = j_0 - k
        if est_valide(i, j):
            marque_case(i, j)

# Tests
import doctest
doctest.testmod()

# 1. lecture de l'entrée
grille = [list(input()) for _ in range(8)]

# 2. on marque les cases menacées
for i in range(8):
    for j in range(8):
        if est_reine(i, j):
            marque_grille(i, j)

# 3. on compte les cases non menacées, paisibles donc
nb_paisibles = 0
for i in range(8):
    for j in range(8):
        if est_libre(i, j):
            nb_paisibles += 1
print(nb_paisibles)

Solution alternative⚓︎

🐍 Script Python
"""
author: Sébastien HOARAU
"""

REINE = 'X'
IBRE = '.'
DANGER = 'o'
DIRECTIONS = (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)

def est_marquee(echiquier, i, j):
    return echiquier[i][j] == DANGER

def est_reine(echiquier, i, j):
    return echiquier[i][j] == REINE

def est_valide(i, j):
    return 0 <= i < 8 and 0 <= j < 8

def dans_une_direction(echiquier, i, j, direction):
    """Marque à partir de la case i, j et en suivant direction
    les cases vides non marquées non masquées par une autre reine
    """
    delta_i, delta_j = direction
    i, j = i + delta_i, j + delta_j
    nb_marquees = 0
    while est_valide(i, j) and not est_reine(echiquier, i, j):
        if not est_marquee(echiquier, i, j):
            echiquier[i][j] = DANGER
            nb_marquees += 1
        i, j = i + delta_i, j + delta_j
    return nb_marquees

def marquer_et_compter(echiquier):
    """Parcours l'échiquier et à partir d'une reine compte et marque les cases
    en danger. La réponse est alors 64 moins le nombre total de cases marquées
    """
    nb_en_danger = 0
    for i in range(8):
        for j in range(8):
            if est_reine(echiquier, i, j):
                nb_en_danger += 1 + sum(dans_une_direction(echiquier, i, j, d) for d in DIRECTIONS)
    return 64 - nb_en_danger