Aller au contenu

Le jeu du Roi

Règle du jeu

  • Sur un échiquier carré de taille donnée, deux joueurs déplacent chacun leur tour un Roi.
  • Trois types de mouvement sur l'échiquier sont autorisés :
    • ← : une case vers la gauche,
    • ↑ : une case vers le haut,
    • ↖ : une case en diagonale, en haut à gauche.
  • Il y a aussi des pions sur l'échiquier ; des obstacles.
  • Le joueur qui ne peut plus jouer a perdu.

Définitions

L'échiquier est carré et de taille quelconque n.

Les cases sont identifiées avec leur ligne puis leur colonne : (i, j).

Ainsi, on aura 1 <= i <= n et 1 <= j <= n pour toute case (i, j) de l'échiquier de taille n. L'indice 0 correspond à un bord de l'échiquier, soit à gauche, soit en haut.

Une position perdante est une position du Roi qui n'autorise aucun nouveau mouvement.

Il ne peut pas y avoir de match nul.

Une position gagnante est une position du Roi qui garantit à un joueur stratège qui commence de pouvoir gagner.

Exemple

. . P . . . . .\nP . . . . . . .\n. . K . . . . .\n. . . . . . . .\n. . . . . . . .\n. . . . . . . .\n. . . . . . . .\n. . . . . . . .

  • Le coin en haut à gauche (1, 1) est une position perdante. Un joueur qui commence là a perdu, il ne peut plus jouer ! On a marqué une croix.
  • Les cases (2, 1) et (1, 3) sont des obstacles, avec des pions.
  • La case (3, 1) est perdante, un joueur qui commence là est bloqué.
  • Les cases (1, 2) et (2, 2) sont gagnantes. Un joueur qui commence là peut jouer en (1, 1) et le joueur suivant perd !
  • La case (3, 2) est gagnante. On peut jouer en (3, 1) et le suivant perd !
  • La case (3, 3) est gagnante. On peut jouer en (2, 3) et le suivant perd ! C'est ce mouvement qui est représenté par la flèche.

Modélisation

Un échiquier est modélisé par une liste de ses lignes.

Chacune de ses lignes est une liste de caractères, où :

  • '0' : indique une position perdante,
  • '1' : indique une position gagnante,
  • '#' : indique le bord en haut ou le bord à gauche de l'échiquier,
  • 'P' : indique un pion.

⚠️ La ligne et la colonne d'indice 0 modélisent le bord en haut et à gauche de l'échiquier, une zone hors jeu.

Modélisation de l'exemple ci-dessus
jeu = [
    ['#', '#', '#', '#', ],
    ['#', '0', '1', 'P', ],
    ['#', 'P', '1', '0', ],
    ['#', '0', '1', '1', ],
]

Exercice

Coder une fonction jeu_roi :

  • qui prend en paramètres :
    • un entier n : la taille de l'échiquier carré,
    • une liste pos_pions de tuple donnant la ligne i et la colonne j de chaque pion.
      • On garantit 1 <= i <= n et 1 <= j <= n, pour chaque pion.
  • et qui renvoie l'échiquier modélisé comme indiqué ci-dessus.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : ∞/∞
.128013],59/f.q78rnb _o=ylaepcwgu)vd4613kRméhtsP(S0+2j[-i:050D0v0N0u0Y0t0O0o0x0t0u0O0O0r010N0Y0w010406050O0A0K0K0u0l0s040R0q0t0A0@0q0m050f0~1012140|0w04051k1d1n0f1k0|0D0Y0C0,0.0:0=0M0Y0z0M0t1B0M0N0`050%0n0t0v1w0/0;011A1C1E1C0N1K1M1I0N0l1l0N0M1O1y010g0)0v0m0u0K0v010,170O0w0u0m0=0U1I1_1{1)1Q1,1M1/1;0`0a0o0P0l0q0w0q0O0Y1a0m0o0#1@0l0l0v0x2i1d200m1l0f1%2v1!1$1#1J0D220=1E0m1.2f1I1t1v0-1P2F0Y2H0m0q2L1I0w2o1l2t2v2Z0}1`2j2N1*2S0l110t0`0o0G2s2%0{2$212)1Q2+2-2/0U2=1{2@2t2E012|0u2.040o0H302u0|332`0=36380o0E3c322%343i2/0d3m3e3o3g350q2,372/0F3t2^2(1x2{3y2}390j3D3f3G3h3I3A390k3M3v3O3x3z3j0e3U2_3W3q040G0S3#3F2O3X3J0G2;1e2?3u3$3.3(0G2 3?313^3-2*3Q380G3b3~3d3E3p430`0G3l473n3_423Y4c3s4f404a4j3)3C4m493w3{3L4s3N3`4b3)3T4x3V4z4p0G3!4D4h3H4p0U3+4J414L3J0U3=2Z4n4u4A0U3}4V4t3%4Y464#4y4i4S4e4*4E4,3R0U4l4/4K3P4M4r2#1q2X1d2L2y0D1$2D3w0x2T1=1l511m4 4}2#570#2Y4:1Q0I0`0#0g3m4$3.0y2/5p4+2{0g0`0V0v0A0p2c0Y5u5j0=0_040Q5F4_350`1c4f5q1*5I0c3m0o5R2{0`2e0O0p0w0Y1b0O5L4Q5H0`0B0Z3t0o5=5W5v0=0O1~04010J1.0C0q0Y1N0.0o0K2T0L1E0O0u2i2k63000L0x1A0i0A620l0o0u0C2p0o1M0+5!2h5(0m0+0z0u0z1/0m0N0v0O013t065?5@5G5N045z0A5V5X0=0q0`0r6R5^015I0W5;6K5?6S6Z0`6#5Q6Y0O0G0`000h006X6M5l040g3y6^5M0m5y6~5,010q5s042Q723p0n0`0l1{0z0v5+345I5K6-6M70045P2Z6L5M6U040T793w0K0Y4c7h3w5I0B0b6$6%7r736`6|0l7w3%0`5E4f7I34757P7p2?7S4u7b047d0m7f7B3W7j7)3`5O7N3.7t7v7R6)7y7A7l5M7D7G7Y7*0`7F4m6J6(6Y7K6}7?6Y7n0I7/1*7U777W317~3`7!7$7(7`737+8n3p7.886M7;8c1Q7^3)7,5S5.5:4m7H5=6)7n6P8A1Q6!8K0=8y4O2#6Y5I0b6,8R7m0`8b8q7C808w6T6V8%016/6;036@8E8F8H5y5A8N6*048V2?8=048Z8W7{808{317@7z048Q8|8S8$8t7s8)9c738,04008.6I838G850`7L8*8p90737n7Q9t7i0`5U9f8r6O8^7|9B3w8e789G7O045!5$6w5*8!7 048D4V8F8i2*8?6Q9R3.8M9#9Y779E928^8I9+04817q6)7t6W9K3.9h000P8/4V069m9X5k9p879=897P8*9I8g2ua23h8k7e7g9(8L0`7k9x7x964U996M5T8*7nab399?0`7=a66M8yap949a045/7}6K6)867M9_9)0Va9769JaA6 af7%aham9Salaq5MaC9/9AaT9u8sa*7Tay8*a%ai5-aG9U3@9WaJ9o775oaN5Y6O8@a=8_932u8}9wa#8o9,b39.b38Ta96V9^a-3w9{6?9/a^3 a`8;a|0Ya~bj3W9{0S9~7X9?aRavadb49-9Z9/b55i6 a8b37t0X8^a;aY9$bbbSaO9/0ba)bAa7b19!bVaj8`bG9*bN0`bPb3bRb99y9:bJ8}aPb-04b/b(8OaobXbZ8hb_b2b~bFbcbMc68Tb^b#b`c6bObQc0be800bbo3dbqbqc4b%b=8#b*c8b,cabUcs9LceczbT9:bg04bib!6M9{0Gbzbpcoa{6_0`0v0*aXcC8B9TaIcO848Xb$bIb+b8aEarcyc*bL9DcjcEa 8(cG8*bxcM3da1aK7c0$0A0lbDcq3D0f5g0v2v2Wd7501u522y2B2w0u1Lda0f510|dk0$0(0*04.