Pourquoi est-il facile de vérifier une grille de sudoku remplie, mais difficile de la remplir ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Quand je résous un sudoku difficile, je peux passer une heure à chercher, alors que vérifier la solution donnée à la fin du journal prend une minute. En NSI, j'ai appris que cette différence entre vérifier et trouver est au cœur d'une des plus grandes questions non résolues des mathématiques et de l'informatique. J'ai voulu la comprendre à partir d'exemples concrets.

L'enjeu et les notions du programme

Comparer le coût de la vérification et celui de la recherche par des dénombrements, et présenter une question ouverte.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Certains problèmes ont une solution facile à vérifier : un sudoku rempli, un emploi du temps sans conflit, une combinaison de variables qui rend vraie une formule logique. Problématique : sont-ils pour autant faciles à résoudre ?

2. 2. Mathématiques : vérifier contre chercher

   4 min

   Vérifier une grille de sudoku $9\times 9$9×9 : chaque ligne, colonne et bloc doit contenir les chiffres de 1 à 9. Il y a 27 groupes de 9 cases ; contrôler chacun demande au plus 9 tests : $27\times 9=243$27×9=243 contrôles. Pour une grille $n^2\times n^2$n²× n², le coût est de l'ordre de $n^4$n⁴ : une puissance, donc « polynomial ».

   Chercher : sans astuce, il faudrait essayer jusqu'à $9^k$9^(k) remplissages pour $k$k cases vides ; avec 50 cases vides, $9^{50}\approx 5\times 10^{47}$9⁵⁰≈5×10⁴⁷. Il existe environ $6,67\times 10^{21}$6,67×10²¹ grilles complètes valides. Pour un problème de satisfaction d'une formule à $n$n variables booléennes, il y a $2^n$2ⁿ affectations à tester : $2^{100}\approx 1,3\times 10^{30}$2¹⁰⁰≈1,3×10³⁰.

   La classe P contient les problèmes résolubles en temps polynomial ; NP, ceux dont une solution se vérifie en temps polynomial. On sait que P est inclus dans NP. Est-ce une égalité ? Personne ne le sait. Si P = NP, chiffrement, logistique et démonstrations seraient bouleversés.

3. 3. NSI : comment on résout quand même

   3 min

   Les programmes de sudoku résolvent les grilles usuelles en millisecondes, par retour sur trace (« backtracking ») : on remplit case par case et on revient en arrière dès qu'une contradiction apparaît. L'élagage évite l'immense majorité des combinaisons.

   Mais pour des grilles géantes ($n^2\times n^2$n²× n² avec $n$n grand), aucun algorithme connu n'est garanti polynomial : le sudoku généralisé est « NP-complet », comme le sac à dos ou le voyageur de commerce. Résoudre efficacement l'un d'eux les résoudrait tous.

4. 4. Conclusion

   1,5 min

   Vérifier un sudoku coûte 243 contrôles, le résoudre peut demander d'explorer un espace gigantesque. La question P = NP demande si cette différence est inévitable : c'est l'un des sept problèmes du millénaire. J'ouvre sur la cryptographie, qui parie justement que certains problèmes faciles à vérifier sont difficiles à résoudre.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Affirmer que P ≠ NP est démontré.
• Croire que tout sudoku est difficile en pratique.
• Confondre nombre de grilles complètes et nombre de remplissages à essayer.

Revoir les notions

• Combinatoire et dénombrement (Terminale spé maths) →
• Fonction exponentielle (Terminale spé maths) →

Autres questions : logique et calculabilité

• Peut-on écrire un programme qui détecte tous les programmes qui tournent en boucle infinie ?
• Existe-t-il des nombres qu'aucun programme ne pourra jamais calculer ?
• Combien de fonctions logiques différentes peut-on construire avec n entrées, et peut-on toutes les réaliser avec ET, OU, NON ?
• Pourquoi « non (a et b) » ne veut-il pas dire « non a et non b », et pourquoi cette erreur cause-t-elle tant de bugs ?

Toutes les questions maths-nsi →