Comment presser un citron (préambule).

« La simplicité est la sophistication suprême » (Léonard de Vinci).

Problème : vous avez à trouver, en seulement quelques secondes, un enregistrement unique parmi des milliards de milliards de possibilité et les seules informations dont vous disposez pour faire votre recherche sont de 17 à 35 attributs sur les 81 que contiennent la donnée tant convoitée… Est-ce possible ? Comment faire? De prime abord, ça semble impossible!

« Impossible n’est pas français » comme le dit le dicton (faussement attribué à Napoléon Bonaparte, vexé par le pessimisme de Jean Léonard, comte le Marois).

Il y a bientôt quelques années de cela, un de mes confrères de travail, Claude, m’introduisait au Sudoku. Au tout début, je ne comprenais pas la fascination de celui-ci pour un problème aussi trivial jusqu’à ce que j’essaie de résoudre une de ces grilles par moi-même… Les règles étant si peu nombreuses et si simples, j’ai rapidement été surpris par la complexité demandée pour résoudre ces puzzles. Et j’en suis devenu accroc!

Binary Sudoku

Non, aucun autre puzzle ne semble, en apparence, aussi simple que le Sudoku! Mais derrière ce petit jeu aux règles minimales se cache un univers de complexité qui englobe une branche complète des mathématiques.

Ce n’est que lorsque je me suis buté à un problème difficile (sans arriver à le résoudre) que je me suis intéressé à l’aspect algorithmique de la résolution d’un Sudoku. Évidemment, j’aurais pu télécharger des « sudoku solver » écrits en Java, en Python, en Ruby, en Smalltalk, en BASIC, en T-SQL, en macros Excel, en n’importe quoi et trouver la solution mais le défi était d’écrire moi-même un de ces « sudoku solver ».

Malheureusement, après réflexion, la tâche m’apparaissait trop simple pour être intéressante. Coder un tel outil avec les méthodes de résolution de base et y ajouter une pile de recherche pour y faire du « backtracking » était, en soi, trop facile (du moins, en Smalltalk) pour valoir la peine. Mais à cette époque, étant plongé dans des requêtes SQL dignes des pires labyrinthes pour régler une foule de problèmes au niveau de la base de donnée d’un de nos clients, l’idée m’est venue de trouver une solution « 100% SQL », sans procédures stockées, sans fonctions, seulement UNE requête SQL. Le défi était lancé!

Il est maintenant établi qu’il existe 6670903752021072936960 grilles différentes pour un Sudoku standard de 9×9. Avec les années, plusieurs raffinements et subtilités ont pris en compte les symétries ainsi que diverses particularités des autres variantes du Sudoku pour mieux comprendre et étudier tous les aspects du Sudoku standard. Diverses techniques de résolution, de plus en plus complexes et élaborées, ont vu le jour puis ont été étudiées et améliorées de fond en comble. Les grilles de Sudoku et les carrés latins ont depuis longtemps tenu les mathématiciens occupés et, encore aujourd’hui, de nombreux trésors et concepts mathématiques encore cachés ne demandent qu’à être découverts. Ce petit jeu représente une mine intarissable de surprises pour les mathématiciens et les développeurs : il ne reste qu’à creuser encore plus creux et plus longtemps!

Cet article, divisé en trois parties, s’attaquera aux grilles de Sudoku standard de 9×9, question de garder les choses simples. Nous examinerons une manière de résoudre ces grilles à l’aide d’une solution n’impliquant que du SQL, sans procédure stockée ni script ni fonction : seulement du SQL bête et méchant!

En première partie nous verrons comment créer les données et tout ce dont nous avons besoin pour poursuivre. En seconde partie, nous tenterons d’optimiser notre approche. En troisième partie, nous mesurerons l’impact des différentes optimisations en les comparant.

Mais avant de débuter, vous devez à tout le moins être familier avec les règles du Sudoku standard, les méthodes de résolution et connaître le jargon du métier!  Tout ce dont vous avez besoin savoir se trouve ici.

Matériel nécessaire : une base de données MySQL (bien qu’avec un peu de débrouillardise, vous pouvez adapter les scripts SQL pour un autre SGBD).

Matériel facultatif: si vous désirez expérimenter vous-même et peut-être pousser l’aventure plus loin, un langage de programmation vous permettant de générer des données et/ou des requêtes SQL pourrait s’avérer utile.  Pour vous aider à apprendre Smalltalk (avec Pharo), je vous conseille fortement Pharo par l’exemple.

Dans cette série d’articles, j’utiliserai MySQL 5.1.53 ainsi que Pharo 1.2a.