Zeytuncu : la difficulté d'un puzzle est déterminée par « le nombre de chiffres utilisés » — lu par Fukai

Résumé en un paragraphe

Les puzzles « de type Numbers » — construire un nombre cible à partir de plusieurs entiers positifs en utilisant uniquement les quatre opérations (le tour des chiffres du Countdown britannique et le Compte est bon français en sont les exemples emblématiques). Cet article tente d'expliquer d'où vient la « difficulté » de ces puzzles, non pas à partir des données de jeu des joueurs, mais à partir de la structure même des puzzles. L'auteur a créé un solveur dédié qui résout exactement si la cible est atteignable par les quatre opérations, a généré environ 3,47 millions d'instances et a défini la difficulté comme le « nombre minimal d'opérations (le nombre minimum d'opérations nécessaires pour atteindre la cible) ».

La découverte centrale est limpide : une seule quantité structurelle — le nombre de chiffres d'entrée effectivement utilisés dans la solution minimale (combien des chiffres disponibles sont utilisés) — détermine parfaitement la difficulté telle que définie ici. L'apprentissage automatique utilisant des statistiques superficielles (taille des chiffres, valeur cible) manque les « puzzles faciles », mais l'ajout du « nombre de chiffres utilisés » rend la classification parfaite. L'auteur appelle cela la « statistique suffisante minimale de la difficulté (l'indice nécessaire et suffisant pour la prédire, qu'on ne peut plus réduire) ». Cet article a pour but de permettre d'en saisir les points essentiels sans ouvrir le texte original.

Introduction

L'auteur est Yunus E. Zeytuncu (Université du Michigan-Dearborn). Cet article a été publié en préimpression (manuscrit pré-révision) sur arXiv (soumis en mars 2026), mais le texte précise explicitement qu'il a été accepté à la conférence internationale AIED 2026 (Artificial Intelligence in Education) traitant de l'IA dans l'éducation — il s'agit donc d'une recherche ayant passé la révision par les pairs. Il est néanmoins précisé que la version préimpression d'arXiv a été consultée pour cet article.

Pourquoi ai-je choisi cet article aujourd'hui ? Je parcours chaque matin les nouvelles publications arXiv, et si le sujet de « mesurer la difficulté » est un thème éternel pour les créateurs de puzzles, il est généralement estimé a posteriori à partir de « données de résultats » comme le taux de succès ou le taux d'abandon des joueurs. Cet article fait le chemin inverse, en essayant d'expliquer la difficulté à partir du contenu même des problèmes. De plus, le sujet porte sur les puzzles « combiner des chiffres pour construire une cible » que tout le monde a touchés au moins une fois. J'ai senti que c'était concret et immédiatement applicable, c'est pourquoi je l'ai choisi.

Contexte

Dans les systèmes d'apprentissage adaptatif (mécanismes qui adaptent les exercices proposés au niveau de maîtrise de l'apprenant), la question de comment déterminer la difficulté des exercices est centrale. Des exercices trop faciles apportent peu d'apprentissage, des exercices trop difficiles brisent la motivation. C'est exactement la même problématique que dans la conception de la difficulté des jeux de puzzle : comment estimer à l'avance le niveau de challenge juste ?

Cependant, de nombreuses méthodes passées ont traité la difficulté comme « une étiquette estimée a posteriori à partir de données de performance telles que le taux de bonnes réponses et le temps de résolution ». Autrement dit, il fallait attendre que de nombreuses personnes jouent avant de connaître la difficulté, et de plus, « pourquoi cet exercice est difficile » restait inexpliqué. Ce que l'auteur interroge, c'est : peut-on définir la difficulté à partir de la structure même du problème, avant de regarder les performances ? Si c'est possible, on peut estimer la difficulté d'un nouveau problème avant que quiconque y joue.

Approche / méthode

Le puzzle traité par l'auteur est baptisé « 4OPS » (four operations, quatre opérations arithmétiques). On donne plusieurs entiers positifs et un nombre cible, et on demande si on peut atteindre la cible avec uniquement addition, soustraction, multiplication et division. Les contraintes : seuls les entiers sont autorisés ; chaque chiffre ne peut être utilisé qu'une fois ; les résultats intermédiaires doivent toujours être des entiers positifs, la soustraction ne peut pas donner un résultat négatif, la division n'est autorisée que si elle tombe juste. Et il n'est pas nécessaire d'utiliser tous les chiffres disponibles (on peut n'en utiliser qu'une partie). L'auteur indique que cette forme autorisant l'utilisation partielle permet d'extraire des différences structurelles plus fines.

L'auteur a d'abord créé un solveur dédié qui résout exactement si la cible est atteignable, en utilisant la programmation dynamique (méthode qui mémorise les réponses aux sous-problèmes déjà calculés et les combine pour résoudre l'ensemble), pour enregistrer les valeurs atteignables et leur « nombre minimal d'opérations ». Il reconstruit également le contenu — c'est-à-dire quels chiffres ont été effectivement utilisés, le « témoin (witness, la construction de la solution minimale elle-même) » — de la formule qui construit la cible avec le minimum d'opérations. C'est là la clé des découvertes ultérieures.

L'ensemble de données est ensuite constitué. Les chiffres disponibles sont au nombre de six : cinq chiffres à un chiffre de 1 à 9 (avec répétition possible) et l'un de 25, 50, 75 — une composition presque identique au tour des chiffres de Countdown. Après déduplication, 3 861 combinaisons, et la cible couvre tous les nombres à trois chiffres de 100 à 999. En croisant les deux, on obtient 3 474 900 instances de problèmes. Chacune est annotée par le solveur avec l'étiquette exacte (résoluble ou non / nombre minimal d'opérations / caractéristiques structurelles). La difficulté est découpée en quatre niveaux selon le nombre minimal d'opérations : facile (0–2 opérations), moyen (3–4 opérations), difficile (5 opérations), insoluble.

Résultats

D'abord la vue d'ensemble. Environ 87 % des problèmes sont résolubles. La distribution de difficulté est asymétrique : les problèmes faciles (0–2 opérations) sont relativement rares, et les problèmes moyens (3–4 opérations) et difficiles (5 opérations) constituent la majorité. Les combinaisons permettant d'atteindre la cible en peu d'opérations sont en réalité peu courantes.

Que donne alors l'apprentissage automatique utilisant uniquement des caractéristiques superficielles (statistiques construites à partir des chiffres disponibles et de la valeur cible) ? Pour prédire si un problème est résoluble, la régression logistique (méthode de classification linéaire simple) atteint environ 90 % de précision. Mais la classification par difficulté est nettement plus difficile, et même le gradient boosting (méthode qui renforce progressivement des prédicteurs faibles) n'atteint qu'environ 73 %, manquant systématiquement les « problèmes faciles ». L'auteur conclut que la facilité ne peut pas être capturée par les statistiques superficielles et dépend des détails de construction de la solution.

On extrait donc des caractéristiques structurelles à partir du « témoin » de la solution minimale : le nombre de chiffres utilisés, les types d'opérations utilisées, la magnitude des nombres intermédiaires, le nombre de solutions minimales existantes, etc. L'ajout de ces caractéristiques améliore spectaculairement la classification de difficulté, et l'auteur rapporte une précision parfaite vis-à-vis des étiquettes de difficulté définies par le solveur.

Et le coup de grâce. Les résultats d'une analyse d'ablation (expérience vérifiant quelle partie de la conception est efficace en éliminant les éléments un par un) montrent que l'ajout du seul nombre de chiffres utilisés dans la solution minimale (que l'auteur appelle minimal input usage) permet de prédire parfaitement toutes les classes de difficulté. Ajouter d'autres caractéristiques n'améliore plus rien. L'auteur appelle cela la « statistique suffisante minimale de la difficulté sous cette définition ». En termes structurels : les problèmes faciles se résolvent avec peu de chiffres, les problèmes difficiles nécessitent de combiner presque tous les chiffres.

Utilisations pratiques

Pour un créateur de puzzles, la première utilisation est l'annotation automatique des étiquettes de difficulté. Si je produis en masse des puzzles de type Numbers (forme où l'on construit une cible à partir de chiffres donnés), je n'ai qu'à faire tourner le solveur une fois par problème généré et noter « combien de chiffres la solution minimale utilise-t-elle ». Rien que cela permet d'attribuer les étiquettes facile / moyen / difficile avant que les joueurs y jouent. Inutile d'attendre que les données de taux de succès s'accumulent.

La deuxième utilisation est la « disposition » de la difficulté. L'auteur indique qu'en classant les problèmes par ordre croissant du nombre de chiffres utilisés, on obtient une progression de difficulté explicable et cohérente. C'est un indicateur directement utilisable pour le passage du tutoriel au mode principal, ou pour alourdir légèrement chaque jour le puzzle quotidien. Le fait que le créateur lui-même puisse expliquer « pourquoi dans cet ordre » a une vraie valeur.

La troisième utilisation est le contrôle côté génération. Si je fais tourner une PCG (génération procédurale de contenu) pour des puzzles hypercasuels, je peux viser à générer des « problèmes résolubles avec 2 chiffres » pour créer des niveaux faciles, et des « problèmes nécessitant les 5 chiffres » pour créer des niveaux corsés — pas mesurer la difficulté après coup, mais la cibler dès le départ.

De plus, j'estime que le champ d'application ne se limite pas aux puzzles de type Numbers. L'idée de « combien d'éléments la solution minimale doit-elle combiner simultanément » se traduit en quantités structurelles comme « combien d'intuitions indépendantes la séquence correcte requiert-elle » pour les puzzles de type Sokoban, ou « combien de chemins la solution doit-elle établir simultanément » pour les puzzles de câblage et de routage. C'est une façon de mesurer la difficulté non par la longueur des étapes, mais par le nombre d'éléments à coordonner simultanément.

Limites

Commençons par les faiblesses que l'auteur lui-même reconnaît. La difficulté ici est fondée sur le « nombre minimal d'opérations défini par le solveur », et la correspondance avec la difficulté réellement ressentie par les êtres humains est explicitement mentionnée comme une question pour des recherches futures. Le nombre de chiffres utilisés capture la nécessité structurelle, mais n'explique pas les facteurs influençant les performances humaines comme la fluidité de calcul, la familiarité avec la stratégie, ou l'état d'esprit du moment. Les résultats sont également explicitement limités au cadre de ce puzzle arithmétique entier.

Ce que Fukai soulève ici, c'est la façon de recevoir les formules fortes que sont « précision parfaite » et « statistique suffisante minimale ». La difficulté est définie par le nombre minimal d'opérations, et le nombre de chiffres utilisés est une quantité également extraite de la même solution minimale (témoin). Les deux sont donc proches de différentes vues d'une même structure, et que l'une prédit presque parfaitement l'autre est, dans une certaine mesure, une nécessité définitionnelle. Ce n'est pas un défaut, mais l'interprétation précise est : non pas « avoir prédit la difficulté ressentie par les humains », mais « la définition de difficulté sur le solveur peut se condenser en une seule quantité structurelle ».

Un autre point : le nombre de citations est encore quasi nul, c'est une nouvelle préimpression qui n'a pas encore été largement discutée. La situation de publication des données et du code n'a pas pu être vérifiée en détail à partir du seul texte (l'auteur indique avoir publié le puzzle de base en tant qu'application mobile gratuite). Le fait que le scope soit limité au format spécifique des puzzles de type Numbers inclus, il faudra vérifier à nouveau avec ses propres sujets pour généraliser à d'autres puzzles.

La lecture de Fukai

Ce qui suit est mon interprétation personnelle. Je souhaite positionner cette recherche comme un petit mais symbolique pas en avant, de l'époque où « on mesure la difficulté à partir des résultats » vers l'époque où « on conçoit la difficulté à partir de la structure ». Dans le vocabulaire de la critique de design, c'est une tentative de ramener la discussion sur la « difficulté » dans le level design, des statistiques de playtest vers la structure même de la solution. Longtemps, nous avons parlé de difficulté en termes de « combien les joueurs ont bloqué ». Mais cet article démontre par le calcul que, du moins pour certains types de puzzles, la difficulté se ramène à la charge cognitive de « combien d'éléments doit-on faire tourner simultanément en main » (la quantité d'informations à retenir et manipuler en même temps). C'est mon interprétation, mais je l'ai reçue comme un pont potentiel : quantifier depuis la structure du puzzle le vieux concept psychologique de la charge de la mémoire de travail (la fonction mémorielle qui retient et manipule des informations pendant un court laps de temps).

Pour aller plus loin

Pour ceux qui veulent approfondir. Si l'on veut voir l'approche classique qui estime la difficulté « à partir des données des joueurs », l'étude empirique sur la modélisation de la difficulté des puzzles mobiles (Difficulty Modelling in Mobile Puzzle Games, 2024) offre une carte complémentaire. Là où cet article attaque « depuis la structure », celui-là attaque « depuis les résultats ». En les mettant côte à côte, on voit se dessiner une structure en tenaille qui encercle l'insaisissable difficulté par deux directions.

De plus, si l'idée du nombre minimal d'opérations de la solution a éveillé de l'intérêt, consulter également l'article de théorie sur la complexité de calcul des expressions arithmétiques (comment la présence ou l'absence de parenthèses change les nombres atteignables, 2021) serait utile pour comprendre la base théorique sur laquelle s'appuie cet article. Comme cet article penche vers « l'implémentation et l'application pédagogique », le combiner avec la carte du côté théorique donne une vision tridimensionnelle.

Références

Articles et ressources associées consultés pour cet article :

・4OPS: Structural Difficulty Modeling in Integer Arithmetic Puzzles (Yunus E. Zeytuncu, 2026, arXiv:2603.25356 preprint / accepté à AIED 2026)

・Recherche associée : Difficulty Modelling in Mobile Puzzle Games (2024, arXiv:2401.17436)

・Recherche associée : The Computational Complexity of Finding Arithmetic Expressions With and Without Parentheses (2021, arXiv:2110.14045)