Le démineur, jeu de réflexion dont le but est de localiser des mines cachées dans une grille représentant un champ de mines virtuel, avec pour seule indication le nombre de mines dans les zones adjacentes est désormais porté en python sur ta NumWorks !

Souvenir de jeunesse

J’ai découvert la programmation sur une désormais antique Casio 9960GT, propulsé par son CPU 8 bits à 4,3 MHz. Lycéen et autodidacte, j’ai alors entrepris de créer un démineur sur ma calculatrice et cela fut pour moi une découverte de différents concepts en algorithmique.

Le processeur de cette génération de calculatrice était tellement lent et l’accès à la mémoire encore plus lent que chaque test logique prenait un temps considérable. Le démineur codé et parfaitement fonctionnel se montrait ainsi d’une lenteur remarquable au premier lancement lors de l’affichage de la couche graphique, il fallait près de 42 secondes pour initialiser la couche graphique.

Quelques caractéristiques de ce démineur :

• 5 niveau de difficulté
• un plateau de jeu de 14 cases par 7, soit 98 cases en tout.
• L’initialisation de la couche graphique prenait à elle seule plus de 30 secondes
• La navigation était fluide, mais la fonction découverte pouvait prendre une bonne dizaine de seconde.

Sur une NumWorks, en Python

20 ans plus tard, l’idée est donc de coder un nouveau démineur, en python, et de le faire tourner sur la calculatrice à la mode du moment : une NumWorks, propulsé par un CPU ARMv7 à 100 / 200 mhz, donc probablement plus de 50 fois plus rapide que celui de mon antique Casio.

Mes élèves de seconde étant tous équipés de cette calculatrice, ils pourront s’amuser en silence quand les cours sont trop ennuyeux, et cela montrera aux futurs élèves de la spécialité NSI les possibilités de la calculatrice et la souplesse du langage python.

L’objectif est de sortir ce démineur pour la sortie officielle de la version 13 de Epsilon, le logiciel sous licence CC BY-NC-SA de la calculatrice NumWorks. La version 13 de Epsilon introduit beaucoup d’améliorations et de nouveautés à l’application Python, celle qui nous intéresse particulièrement et le getkey, la capacité de la calculatrice dans un script python à détecter si une touche est pressée.

Le site tiplanet.org ayant déjà bien documenté cette fonctionnalité, on dispose donc déjà des codes associés aux touches :

Créer une interface graphique

Pour faire un démineur, on a besoin d’un tableau de n lignes et p colonnes dans lequel on va afficher une mine, un drapeau ou un chiffre.

Il faut donc s’adapter à la résolution de l’écran, et la principale contrainte à prendre en compte est la taille d’affichage des chiffres.

Puis on les met en couleur

et enfin on code les mines et le drapeau.

#codage des couleurs
co=color
f,h,n = 255,127,0
c=[co(f,f,f), co(45,125,210), co(151,204,4), co(238,185,2), co(244,93,1), co(215,65,167), co(n,n,n), co(n,n,n), co(n,n,n),
   co(h,h,h),co(192,192,192),co(96,96,96),co(253,236,185)]

def terrain(): #Affiche la grille
  fill_rect(8,21,300,200,c[9])
  for y in range(21,243,20):
    for x in range(8,309):
      set_pixel(x,y,c[10])
  for x in range(8,320,20):
    for y in range(21,222):
      set_pixel(x,y,c[10])

def cl(x,y):
  fill_rect(9+20*x,22+20*y,19,19,c[0])
 
def drapeau(x,y):
  fill_rect(17+20*x,26+20*y,3,9,c[12])
  fill_rect(17+20*x,36+20*y,3,3,c[12])
 
def mine(x,y): # Ce code ne sera pas retenu pour la version finale.
  cl(x,y);
  fill_rect(12+20*x,36+20*y,13,4,c[9])
  fill_rect(14+20*x,34+20*y,9,2,c[11])
  fill_rect(17+20*x,32+20*y,3,2,c[5])

Une matrice pour stocker les mines

Le plus simple est de stocker les mines dans une matrice 10×15.
Pour cela on défini une matrice en python et on la rempli de 0.

m = [[0 for y in range(10)] for x in range(15)]

puis un script génère des bombes, codées 999 dans la matrice.

def gvt(): #fonction renommée depuis ...
  b = 20
  while b>0:
    x, y = randint(0,14),randint(0,9)
    if m[x][y]!=999:
      m[x][y]=999
      b-=1
      for p in range(max(0,x-1),min(15,x+2)):
        for q in range(max(0,y-1),min(10,y+2)):
          if m[p][q]!=999:m[p][q]+=100  

Le script ci-dessus a deux fonctions, il place les 20 mines puis « calcule » pour chaque case le nombre de bombes dans les 8 cases autour.

Ainsi, la matrice contient à ce stade uniquement des entiers :
soit des 0 (0 bombes dans les 8 cases environnantes), soit des multiples de 100, soit des 999.

Pourquoi 100 et pas 1 pour indiquer qu’il y a une bombe ?

Car on va utiliser cette matrice pour y stocker une information importante, à savoir si la case a été découverte ou pas.

Calcul du nombre de mines de chaque case

En parcourant l’article Wikipédia sur le démineur lors de la rédaction de ce compte rendu, j’y ai découvert que j’ai construit intuitivement l’un des deux algorithmes classiques pour le calcul des nombres des différentes cases du démineur.

Sur mon antique Casio 9960GT, j’utilisais l’algorithme par case :

explorer tableau par case
si case est vide
nombre := compter_mines(case.voisinage)
case.valeur = nombre<

et sur la NumWorks, j’ai construit une version légèrement adapté de l’algorithme par mine :

// Placement de la mine
explorer mine.voisinage par case
si case est vide
incrémenter case.valeur

Dans une première version en python, j’utilisais la partie décimale pour y stocker le 42 ou le 0.01, ainsi cela donnait 1,42 si il y a une mine dans le voisinage et que la case est déjà découverte, mais ceci posa un problème, le test :

if 1.42-round(1.42)==42

ne marchait pas, car python ne dispose pas d’un moteur de calcul exact sur les réels.
Le résultat du calcul 1.42-1 en python est 0.419999999999999

Par ailleurs, stocker en réel et non un entier est susceptible de consommer plus de mémoire, donc le stockage de l’information sous la forme d’entier est préférable pour les tests conditionnels.

Une fonction pour les découvrir toutes !

A partir de la matrice, on peut exécuter un script qui révèle les positions et vérifie que tout fonctionne correctement :

def verif():
  for x in range(15):
    for y in range(10):
      if m[x][y]==666:
        mine(x,y)
      elif m[x][y]>0:
        chiffre(x,y)

La fonction chiffre elle a pour objectif d’afficher le nombre de bombes autour :

def chiffre(x,y):
  cl(x,y)
  nb[1]+=(m[x][y]%100!=42)
  i=m[x][y]-m[x][y]%100
  m[x][y]=i+42
  if i>=100:v=int(i/100);draw_string(str(v),13+20*(x),23+20*(y),c[v],c[0])
  deminage()

pas à pas de la fonction chiffre :

• cl(x,y) éclairci la case
• nb[1] s’incrémente de 1 si la case n’a pas déjà été découverte, c’est le compteur de la victoire
• Si la valeur m[x][y] contenait Z00 elle sera désormais de Z42, Z étant un entier entre 0 et 8.
• On affiche la valeur de Z, avec une couleur adaptée.
• On exécute le script deminage(), qui calcule le score et vérifie si l’on a gagné.

Le plus difficile à coder est la fonction de découverte de proche en proche, si on dévoile une case ne contenant aucune mine, et pas de mine non plus dans les 8 cases alentours, il faut faire un « script récursif » de traitement et de découverte de ces cases.

La fonction decouvre() est la suivante :

def decouvre(x,y):
  i=1
  while i>0:
    chiffre(x,y)
    for p in range(max(0,x-1),min(15,x+2)):
      for q in range(max(0,y-1),min(10,y+2)):
        if m[p][q]>=100:chiffre(p,q)
        elif m[p][q]==0:m[p][q]+=1
    i=0
    for p in range(15):
      for q in range(10):
        if m[p][q]%100==1:i=1;x=p;y=q;p=14;q=9

Elle est appelée par la fonction marche() :

def marche(x,y):
  if m[x][y]>=999:explose()
  elif m[x][y]>=100:chiffre(x,y)
  else:decouvre(x,y)

Ainsi la fonction découverte n’est appelée que si on « marche » sur une case sans mine, et que les 8 cases aux alentours ne contiennent également aucune mine.

Elle teste les 8 cases du voisinage, affiche le chiffre de celles qui doivent afficher un chiffre. Si les cases contiennent un 0, il devient 1 et devra être traité par le script ultérieurement.

Ce fonctionnement n’est pas optimal en temps de calcul, mais il ne crée aucun nouvel objet en mémoire. Il n’est pas vraiment non plus récursif au sens python pour éviter là encore de consommer trop de mémoire.

Une précédente version ajoutait les coordonnées des cases à traiter dans une liste, mais cette liste grossissait et pouvait saturer la mémoire.

Piloter un drone sur un terrain miné

Il ne reste plus qu’à coder la navigation dans l’écran, c’est à dire l’interaction entre l’affichage et le clavier de la calculatrice.

a,r,t,l,k,s=set_pixel,fill_rect,draw_string,range,keydown,sleep
p=[[6,5],[7,5]]
 
def survol():
  x, y = p[1][0], p[1][1]
  v = m[x][y]
  gps(x,y)
  # t(str(int(v/100)),20,2)
  x, y = p[0][0], p[0][1]
  v = m[x][y]
  if p[1][0]!=x or p[1][1]!=y:
    if (v-42)%100==0:gps(x,y,0)
    else:gps(x,y,9)
  del p[0]
 
def gps(x,y,i=6):
  r(9+20*x,22+20*y,19,2,c[i])
  r(26+20*x,22+20*y,2,19,c[i])
  r(9+20*x,22+20*y,2,19,c[i])
  r(9+20*x,39+20*y,19,2,c[i])
 
def drone():
  while not k(6):
    if k(0):p.append([max(p[0][0]-1,0),p[0][1]])
    if k(3):p.append([min(p[0][0]+1,14),p[0][1]])
    if k(1):p.append([p[0][0],max(p[0][1]-1,0)])
    if k(2):p.append([p[0][0],min(p[0][1]+1,9)])
    if k(4):marche(p[0][0],p[0][1])
    if k(17) or k(16):drapeau(p[0][0],p[0][1])
    if k(52):nb[2]=0;nb[0]=22;minage(nb[0]);s(1)
    if k(45):nb[0]=min(nb[0]+5,90);minage(nb[0]);s(1)
    if k(46):nb[0]=max(nb[0]-5,10);minage(nb[0]);s(1)
    if len(p)>1:survol();s(0.120)

La fonction survol() déplace le curseur, en rétablissant l’affichage de la case précédemment survolée à l’aide de la fonction gps().

la fonction drone() attend que l’utilisateur appuie sur une touche du clavier.

Le nombre de mine par défaut est fixé à 19 pour un plateau de 150 cases, soit un ratio de 12.7%.

Le démineur de Microsoft sur Windows 10, appelé Minesweeper propose des ratios de 11,1%, 15%, et 20% respectivement pour les modes faciles, moyen et difficile.

Le nombre de mine qu’il est possible de placer est un nombre dans la liste :
13, 16, 19, 22, 25, …, 40 mais une petite astuce mathématiques permet de choisir n’importe quel entier entre 11 et 42 pour désigner le nombre de mine.

Oui n’importe quel nombre entier entre 11 et 42 alors que l’interface et l’utilisation des touches [+] et [-] ne permet que d’ajouter ou d’enlever 3 mines…

Epsilon version 13.2

La sortie de la version 13.2.0 d’Espilon, le logiciel qui anime la NumWorks permet de faire tourner sans problème ce démineur. Si dans la version 13.0.0 et 13.1.0 le démineur ne fonctionnait pas à cause d’une affectation insuffisante de mémoire pour l’exécution des scripts python, la version 13.2.0 résout ce problème qui n’est plus qu’un mauvais souvenir. Ainsi, la NumWorks est l’une des calculatrice la plus rapide lors de l’exécution des scripts Python, et que pour un prix d’achat de 79€ elle n’a clairement aucune concurrence dans cette gamme de prix.

Omega, un firmware alternatif pour votre NumWorks

Le logiciel de la NumWorks est libre et ouvert, ce qui est très appréciable et on peut même dire admirable dans l’univers très fermé des calculatrices.

Ainsi, tout le monde peut accéder au code source, le lire, le modifier et le redistribuer en respectant les conditions imposées par la licence CC BY-NC-SA.

Une équipe de passionné a donc décidé de développer un firmware alternatif, et il l’ont appelé Omega. Ils intègrent différentes amélioration, et poussent les developpeur du firmware stock à s’améliorer sans cesse.

Pour tester ce démineur, tu dois :

• Soit mettre à jour ta calculatrice en version 13.2.0 au minimum.
• Soit installer le firmware Omega.

Le démineur en version 1.20

Une nouvelle version de ce démineur est sortie le 18 avril 2020, elle intègre un menu graphique python développé en interne pour cette occasion.

Le script du démineur pèse désormais 8.42ko, et le démineur peut désormais être paramétré par un menu graphique, interactif et intuitif.

De nouvelles options ont été ajoutées :

1. Le choix du graphisme : Flat vs Classique
2. Un mode triche à tester avec la touche MAJ de l’ordinateur ou Shift sur la calculatrice.

Quelques dernières remarques

Si tu souhaites réagir à cet article, tu es invité à le faire sur ce forum :
[tiplanet.org] Un démineur en python pour la NumWorks, tu y trouvera des discussions pointues sur l’utilisation de la mémoire lors de l’éxécution d’un script Python.

Entre le script initial et le script proposé en ligne à cet instant, de nombreuses réécritures portions du code ont été réécrites, mais les explications de cet article restent valables.

Vincent ROBERT

Enseignant de mathématiques et de spécialité NSI, Lycée Louis Pasteur d’Avignon.
Aime compter jusqu’à 666 mais s’arrête souvent à 42.
Auteur du livre Découvrir la calculatrice NumWorks.

nsi.xyz