Sudokus Arboricoles

Numérotation gracieuse

Il y a quelques semaines, un article sur les sudokus arboricoles est paru sur le site Images des mathématiques. Pour résumer le principe du jeu, sans toutefois vous priver du plaisir de lire l’article d’origine, il s’agit de numéroter les n arêtes et les n+1 sommets d’un arbre (un arbre est un graphe connexe, sans cycle… nous allons y revenir), de manière à n’utiliser que les nombres de 0 à n pour les sommets, et que les nombres de 1 à n pour les arêtes. De plus, une arête devra porter comme étiquette la valeur absolue de la différence des étiquettes des nœuds qu’elle relie. Ainsi, l’arête qui relie les sommets 3 et 7 devra porter l’étiquette 4. Une telle numérotation est dite gracieuse.

Voici à titre d’exemple un arbre numéroté gracieusement :

Déterminer l’existence d’une numérotation gracieuse pour un arbre quelconque est un problème ouvert.

Comme pour les sudokus, on peut partir d’un arbre comportant quelques numéros d’étiquettes déjà fixés et le jeu consiste alors à compléter la numérotation des nœuds et des arêtes.

C’est ce que je vous propose ici. Les arbres proposés ont été générés par un programme écrit en Python, dont l’idée générale est donnée en fin de billet.

Numérotations équivalentes

Remarquons tout d’abord que la place (géométrique) de certains nœud peut être échangée dans l’arbre précédent (par exemple les nœuds 7 et 9) :

Le graphe obtenu est le même dans les deux cas, car ce qui importe est la manière dont les nœuds sont reliés et non l’endroit où ils sont dessinés (vous pouvez imaginer que l’arbre est déformable : on peut déplacer les nœuds et la longueur des arêtes s’adapte automatiquement). Puisqu’on peut permuter les nœuds 3, 6, 8, 7 et 9, nous avons 5!=120 dessins différents, mais qui correspondent tous au même graphe).

Représentation informatique des arbres

Si un graphe est un arbre (pour cela, le graphe doit être connexe, c’est à dire en un seul morceau, et sans cycle), nous pouvons choisir un nœud spécial, qui s’appelle la racine. Chaque arête peut être orientée, de la racine vers l’extérieur, ce qui donne par exemple cette image, si on choisit 0 comme racine de l’arbre :

Dans la suite, nous allons choisir 0 comme racine de l’arbre. Ce choix étant fait il n’y a qu’une seule orientation possible et nous ne la représenterons plus sur les dessins. Cette orientation crée une hiérarchie dans l’arbre. Si une flèche va du nœud 5 au nœud 1, on dit que 5 est le père de 1, et que 1 est un des fils de 5. Dans un arbre, un nœud ne peut avoir qu’un seul père (sinon, il y aurait un cycle). Mais un nœud peut avoir plusieurs fils (le nœud 0 en a 6). De plus, tous les nœuds ont un père sauf la racine (ici 0). Les nœuds qui n’ont pas de fils sont appelés les feuilles (ici 3, 4, 6, 7, 8 et 9).

Voici une manière rapide, à défaut d’être sophistiquée, de représenter un arbre dans le langage Python :

{0: [3, 5, 6, 7, 8, 9], 1: [2], 2: [4], 3: [], 
  4: [], 5: [1], 6: [], 7: [], 8: [], 9: []}

Cette structure de données s’appelle en Python un dictionnaire (c’est la même chose qu’un tableau associatif ou une table de hachage). Il est formé de clés : 0, 1, 2… et à chaque clé est associée une valeur, qui est ici une liste. Chaque clé ne peut figurer qu’une seule fois dans le dictionnaire. Dans l’exemple qui précède, à la clé 0 est associée la liste [3,5,6,7,8,9]. Cela signifie pour nous que le nœud 0 a 6 fils : 3, 5, 6, 7, 8 et 9. De même l’entrée 2: [4] signifie que le nœud 2 a un seul fils, 4. Et les nœuds 8 ou 9 par exemple, n’ont pas de fils (la liste est donc vide). Cette représentation sous forme d’un dictionnaire est donc équivalente au dessin de notre arbre, le choix de 0 comme racine ayant été fait.

Dans la suite, on donnera à chaque fois l’image du graphe, ainsi que sa représentation sous forme de dictionnaire… dans l’hypothèse où certains s’amuseraient plus en faisant un programme qui résout le problème qu’en le résolvant à la main 😎

Jeu de Sudoku arboricole

Pour jouer au Sudoku arboricole, on cache les valeurs de certains nœuds (en les remplaçant par exemple par des lettres). Il faut alors deviner le numéro à mettre à la place de chaque lettre pour obtenir une numérotation gracieuse. Selon les indices qu’on donne, il peut éventuellement y avoir plusieurs solutions. Comme au sudoku, on considère que l’énoncé est réussi s’il n’y a qu’une seule solution (pour les sudokus, la solution doit nécessairement être unique).

Voici un exemple de problème :

{0: [1, 'E', 'F', 'G'], 1: ['A', 'B', 'C', 'D'], 2: [], 
  'F': [2], 'G': [], 'D': [], 'E': [], 'B': [], 'C': [], 'A': []}

Dans cet exemple, il y a effectivement 48 façons différentes d’associer une lettre à un chiffre et obtenir ainsi une numérotation gracieuse, mais elles donnent toutes le même graphe (nous avons vu que ce qui compte est la manière dont les nœuds sont reliés et non le lieu où on les dessine). Dans l’exemple qui précède les nœuds A, B, C, D d’une part et E,G d’autre part jouent le même rôle. Cet énoncé n’a donc qu’un seul graphe solution.

En supprimant l’indice sur le nœud 1, nous obtenons ce nouvel énoncé :

{0: ['A', 'F', 'G', 'H'], 2: [], 'H': [], 'F': [], 'G': [2], 
  'D': [], 'E': [], 'B': [], 'C': [], 'A': ['B', 'C', 'D', 'E']}

Celui-ci a trois solutions (ce n’est donc pas un «vrai» sudoku). La première correspond au premier problème, mais il y en a deux autres obtenues en plaçant d’autres valeurs que 1 à la place du nœud A.

Voici un autre problème, toujours avec 10 nœuds :

{2:['D','E','C'], 1:[2,'F','G','H'], 'G':['B'], 'H':['A'],
   'B':[], 'A':[], 'F':[], 'D':[],'E':[], 'C':[]}

Cette fois-ci c’est le nœud 1 qui a été pris comme racine de l’arbre (dans la représentation sous forme de dictionnaire)

Solutions

Je donnerai les solutions des problèmes donnés plus haut dans un prochain billet, et je proposerai peut être quelques autres problèmes par la même occasion.

Comment générer des arbres numérotés gracieusement ?

Voici la méthode employée ici pour générer les énoncés. La première étape est de construire un arbre numéroté gracieusement. La seconde est de supprimer certaines informations sur les valeurs de nœuds pour transformer la solution en énoncé.

Pour construire une numérotation gracieuse, j’ai opéré ainsi :

1. placer la racine de l’arbre
2. générer des arêtes aléatoirement
3. accrocher les arêtes sur l’arbre

Voyons ce que cela donne pour un graphe ne comportant que 4 nœud (0, 1, 2, 3) et donc trois arêtes de valeurs (1, 2 et 3).

Choisissons par exemple 0 comme racine. Les sommets qu’il reste à placer sont 1, 2, 3 et les arêtes sont 1, 2, 3.

On commence par apparier les arêtes aux sommets, au hasard. Par exemple (le premier nombre est le sommet, le second est l’arête) :

• (1,2)
• (2,1)
• (3,3)

Puis, on tente d’accrocher une de ces arêtes au graphe en conservant la propriété des arêtes (valeur de l’arête égale à la valeur absolue de la différence des nœuds qu’elle relie).

• L’arête (1,2) par exemple, pourrait être reliée au nœud -1 (mais il n’existe pas) ou au nœud 3 (qui n’est pas dans le graphe, il n’y a pour le moment que le nœud 0). On ne peut donc pas accrocher cette arête.
• L’arête (2,1) pourrait être accroché au nœud 1 ou au nœud 3. Aucun ne figure dans le graphe
• La troisième arête pourrait être accrochée au nœud 0 ou au nœud 6 (qui n’existe pas). Le nœud 0 est dans le graphe et on peut donc accrocher cette première arête. On obtient ainsi ce graphe :

Puis on recommence avec les arêtes restantes. L’arête (1,2) peut être reliée au nœud 3. On obtient donc :

Enfin la dernière arête (2,1) peut être accrochée au nœud 1 (ou au nœud 3). On obtient ainsi :

A priori, rien ne garantit qu’on ne va pas être bloqué, avec une liste d’arêtes à placer qui ne peuvent être placées nulle part. Si cela se produit, on peut «mélanger» les associations sommet/arêtes restantes. Là non plus, rien ne garantit qu’on ne se retrouvera pas bloqué. En pratique, ça ne m’est pas arrivé, et j’ai pu construire des arbres numérotés gracieusement assez grands, comme celui-ci, qui comporte 30 nœuds :

ou celui-là qui en contient 100 :

La seconde étape consiste à construire un énoncé en supprimant l’information numérique de certains nœuds, et en faisant en sorte qu’il n’y ait qu’une seule solution. Ce point est plus difficile que le précédent : il faut écrire un programme qui recherche toutes les solutions au problème, afin de vérifier qu’il n’y en a qu’une. Je laisse cette partie en exercice 😎

Solutions

Voici les solutions aux différents problèmes posés plus haut :

Problème 1

Problème 2

Il y a deux solutions en plus de la précédente :

Problème 3