E07 - Échec et mat⚓︎
Le problème
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