Corrigé Mines-Ponts 2026 Informatique commune MP-PC-PSI — Partie 2 (Q1 à Q11) : Quixo à deux joueurs humains : plateau, coups valides, glissements, alignements

Sujet officiel du concours Mines-Ponts, session 2026, épreuve Informatique commune MP-PC-PSI. Corrigé rédigé par Ibrahim Alame.

Sujet officiel (PDF, site du concours)

Énoncé

Le jeu. Plateau $5 \times 5$ de cubes ; chaque cube est neutre, marqué X (joueur 1) ou marqué O (joueur 2). À son tour, un joueur prend un cube du bord, neutre ou à sa marque, puis le réinsère (à sa marque) à une extrémité de la ligne ou de la colonne de la case libérée, en poussant les cubes intermédiaires pour boucher le trou ; le remettre à sa place d'origine est interdit. Aligner cinq symboles (ligne, colonne, diagonale) fait gagner.

Figure 1 — Le plateau de jeu.

Codage. Le plateau est une liste de listes $5 \times 5$ d'entiers : $0$ neutre, $1$ pour X, $2$ pour O ; la case $(0, 0)$ est en haut à gauche. Les fonctions internes de coût linéaire sont interdites (sauf le tranchage).

Figure 2 — Situation de jeu, le joueur 1 doit jouer.

Q1. Écrire initialisation() qui renvoie le plateau $5 \times 5$ entièrement neutre.
Q2. Majorer le nombre de configurations du plateau ; en déduire, par un logarithme, le nombre de bits nécessaires pour les coder par des entiers (le codage naïf utilise $25$ entiers de $16$ bits).
Q3. Sur la figure 2, lister par ligne croissante les cases que le joueur 1 peut choisir.
Q4. Il choisit $(1, 4)$ : où peut-il replacer le cube ?
Q5. Écrire case_bord(i, j) (vrai si la case est au bord) sans énumérer les cases du bord.
Q6. Écrire case_choix_valide(jeu, i, j, joueur), en réutilisant case_bord.
Q7. Écrire case_deplacement_valide(i_d, j_d, i_n, j_n) : la case d'arrivée $(i_{n}, j_{n})$ est-elle permise depuis la case de départ $(i_{d}, j_{d})$ , supposée valide ?
Q8. Le cahier réponse donne deplacement_case(jeu, i_d, j_d, i_n, j_n, joueur) en quatre cas (« mouvement 1 » : $i_{n} < i_{d}$ ; 2 : $i_{n} > i_{d}$ ; 3 : $j_{n} < j_{d}$ ; 4 : sinon). Décrire le glissement des pions dans chaque cas ; prouver la terminaison du mouvement 1 par un variant.
Q9. Compléter les deux lignes manquantes du mouvement 2.
Q10. Écrire alig(jeu, joueur, i, n) : vrai si la ligne $i$ contient $n$ pions consécutifs du joueur ( $1 < n \leq 5$ ), en lisant chaque case une seule fois. (acol, adiag1, adiag2 font de même sur la colonne $j$ et les deux diagonales.)
Q11. Écrire gagnant(jeu, joueur) : vrai si le joueur a un alignement de cinq.

Corrigé

Q1. On construit chaque ligne par une nouvelle liste, pour que les cinq lignes soient indépendantes en mémoire.


def initialisation() -> [[int]]:
    return [[0] * 5 for _ in range(5)]

Ce que le correcteur attend : surtout pas [[0]*5]*5, qui crée cinq références vers la même ligne : modifier plateau[0][0] modifierait toute la colonne $0$ . Le test p = initialisation(); p[0][0] = 7 laisse bien p[1][0] à $0$ . Pas de numpy non plus : le sujet impose une liste de listes.

Q2. Chacune des $25$ cases prend l'une de $3$ valeurs (neutre, X, O), indépendamment si l'on ignore symétries et configurations inaccessibles : au plus

$N = 3^{25} = 847288609443 \approx 8, 5 \times 1 0^{11} configurations.$

Avec $b$ bits on code $2^{b}$ entiers distincts ; il faut $2^{b} \geq N$ , soit

$b = ⌈ lo g_{2} (3^{25}) ⌉ = ⌈ 25 lo g_{2} 3 ⌉ = ⌈ 39, 6 ⌉ = 40 bits,$

avec $lo g_{2} 3 = ln 3/ ln 2 \approx 1, 585$ . Sans calculatrice, la majoration $3 < 4$ donne déjà $3^{25} < 4^{25} = 2^{50}$ : $50$ bits suffisent (on code chaque case sur $2$ bits). Dans les deux cas, on est très loin des $25 \times 16 = 400$ bits du codage naïf : un facteur $10$ environ.

Q3. Le joueur 1 (X) peut prendre une case du bord neutre ou marquée X. En parcourant les $16$ cases du bord de la figure 2 :

$(0, 3), (0, 4), (1, 4), (2, 0), (3, 4), (4, 1), (4, 3) .$

Les autres cases du bord portent un O. (Liste confirmée par case_choix_valide de Q6, exécutée sur le plateau de la figure 2.)

Q4. La case $(1, 4)$ est sur la colonne de droite, hors d'un coin. Le cube se réinsère à une extrémité de sa ligne $1$ ou de sa colonne $4$ , sauf à sa place d'origine $(1, 4)$ :

$(0, 4), (4, 4) (extr e ˊ mit e ˊ s de la colonne 4), (1, 0) (d e ˊ but de la ligne 1) .$

Par exemple, vers $(0, 4)$ , le cube neutre de $(0, 4)$ descend en $(1, 4)$ et X s'installe en $(0, 4)$ .

Q5. Une case est au bord si l'un de ses indices vaut $0$ ou $4$ ; on vérifie aussi qu'elle est dans le plateau.


def case_bord(i: int, j: int) -> bool:
    return 0 <= i < 5 and 0 <= j < 5 and (i == 0 or i == 4 or j == 0 or j == 4)

On renvoie directement l'expression booléenne, sans if ... return True else return False.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →