Les mathématiciens résolvent un problème de sudoku minimum

Le sudoku est un puzzle numérique composé d'une grille de 9 x 9 dans laquelle certaines cellules contiennent des indices sous la forme de chiffres de 1 à 9. Le travail du solveur consiste à remplir les cellules restantes de sorte que chaque ligne, colonne et case 3×3 la grille contient les neuf chiffres.

Il existe une autre règle non écrite : le puzzle ne doit avoir qu'une seule solution. Ainsi, les grilles ne peuvent contenir que quelques indices de départ.

Il est facile de voir pourquoi. Une grille avec 7 indices ne peut pas avoir une réponse unique car les deux chiffres manquants peuvent toujours être intervertis dans n'importe quelle solution. Un argument similaire explique pourquoi les grilles avec moins d'indices doivent également avoir plusieurs solutions.

Mais il n'est pas si facile de comprendre pourquoi une grille avec 8 indices ne peut pas avoir une solution unique, voire une avec 9 indices ou plus.

Cela soulève une question intéressante pour les mathématiciens : quel est le nombre minimum d'indices de Sudoku qui produit une réponse unique ?

C'est une question qui pèse lourdement sur la communauté Sudoku, notamment parce qu'elle pense connaître la réponse. Les fanatiques de Sudoku ont trouvé de nombreux exemples de grilles avec 17 indices qui ont une solution unique mais ils n'en ont jamais trouvé une avec 16 indices.

Cela suggère que le nombre minimum est de 17, mais personne n'a été en mesure de prouver qu'il n'y a pas de solution à 16 indices qui se cache quelque part dans l'espace du puzzle.

Entrez Gary McGuire et ses amis de l'University College Dublin. Ces gars-là ont résolu le problème en utilisant la technique mathématique éprouvée de la force brute pure.

Essentiellement, ces gars ont examiné chaque solution potentielle de 16 indices pour chaque grille de Sudoku possible. Notre recherche n'a révélé aucun puzzle à 16 indices, mais s'il en avait existé, nous l'aurions trouvé, disent-ils.

C'est un exploit impressionnant. Il y a exactement 6 670 903, 752, 021, 072, 936, 960 solutions possibles au Sudoku (environ 10^21) . C'est bien plus que ce qui peut être vérifié dans un délai raisonnable.

Mais comme par hasard, il n'est pas nécessaire de tous les vérifier. Divers arguments de symétrie prouvent que beaucoup de ces grilles sont équivalentes. Cela réduit le nombre à vérifier à seulement 5 472, 730, 538.

McGuire et co ont donc écrit un programme appelé Checker pour vérifier chacune de ces grilles pour une solution à 16 indices.

Mais le processus de vérification d'une seule grille est lui-même délicat. Une façon de le faire est d'examiner chaque sous-ensemble possible de 16 indices pour voir si l'un d'entre eux conduit à une solution unique. Le problème est qu'il y a environ 10^16 sous-ensembles pour chaque grille.

Encore une fois, un peu de mathématiques est utile. McGuire et ses collègues ont utilisé un raisonnement intelligent pour montrer que certains sous-ensembles sont équivalents à de nombreux autres, ce qui réduit considérablement le nombre de sous-ensembles à vérifier.

Néanmoins, le calcul qui en résulte est toujours un monstre. L'équipe de Dublin affirme qu'il a fallu 7,1 millions d'heures-cœurs de temps de traitement sur une machine dotée de 640 processeurs Intel Xeon à cœur hexagonal. Ils ont commencé en janvier 2011 et se sont terminés en décembre.

L'exercice dans son ensemble peut sembler un peu amusant en mathématiques, mais ce type de résolution de problèmes a de nombreuses applications importantes. McGuire et ses collègues disent que le problème de la vérification de la grille Sudoku est formellement équivalent aux problèmes de l'analyse de l'expression des gènes et des tests de réseaux informatiques et de logiciels.

Ainsi, les méthodes de l'équipe de Dublin pour accélérer le calcul auront également un impact direct dans ces domaines.

Mais alors que le résultat est clairement impressionnant, le problème du sudoku minimum n'est pas entièrement résolu.

Ce problème réclame une preuve élégante qui nous permette de voir pourquoi le nombre minimum doit être 17 ; plutôt comme la preuve qu'il ne peut y avoir de solutions uniques pour 7 indices ou moins.

Une grande demande, je sais, mais qui vaut sûrement la peine d'être visée.

Réf : arxiv.org/abs/1201.0749 : Il n'y a pas de sudoku à 16 indices : résoudre le problème du nombre minimum d'indices de Sudoku

Correction : ce message a été édité le 6 janvier pour refléter l'argument selon lequel si une grille à n indices est résoluble de manière unique, l'ajout d'un chiffre pour créer une grille à n+1 indices doit également être résoluble de manière unique. Donc, s'il n'y a pas de grilles de 16 indices résolubles de manière unique, il ne peut pas y avoir de grilles avec moins d'indices résolvables de manière unique. Merci à RealMurph et abooij.

cacher