Aller au contenu

Le graphe Sudoku

Le travail présenté dans cette page est basé sur une idée originale de Mesdames MOUGEOT, REYNAUD et MARTENS et de Monsieur JUNIER, enseignants de NSI dans l'académie de Lyon. Que tous les quatre en soient ici remerciés.

Wikipédia

Le sudoku est un jeu en forme de grille défini en 1979 par l’Américain Howard Garns, mais inspiré du carré latin, ainsi que du problème des 36 officiers du mathématicien suisse Leonhard Euler.

Le but du jeu est de remplir la grille avec une série de chiffres (ou de lettres ou de symboles) tous différents, qui ne se trouvent jamais plus d’une fois sur une même ligne, dans une même colonne ou dans une même région (également appelée « bloc », « groupe », « secteur » ou « sous-grille »). La plupart du temps, les symboles sont des chiffres allant de 1 à 9, les régions étant alors des carrés de 3 × 3. Quelques symboles sont déjà disposés dans la grille, ce qui autorise une résolution progressive du problème complet.

Pour s'échauffer

Tentez de résoudre les 2 grilles de Sudoku de 2×2 ci-dessous :

  1. Grille n°1 Grille n°1

    Une solution

    Solution Grille n°1

  2. Grille n°2 Grille n°2

    Une solution

    Plusieurs solutions sont possibles avec cette grille. En voici une : Solution Grille n°2

Le graphe Sudoku

Convention

Afin de faciliter la manipulation, les grilles seront au format 2 × 2 dans les questions. Toutefois, il ne faut pas oublier que le but des questions est ensuite de généraliser au format 3 × 3, 4 × 4, etc...

Numéroter les cases Afin de représenter le Sudoku sous forme de graphe non orienté, nous allons considérer que les sommets du graphe sont les cases du Sudoku, numérotées de 0 à 15 en allant de gauche à droite et de haut en bas, comme sur la figure ci-contre.

Chaque arête du graphe est placée entre deux sommets liés par une contrainte.

Exemple

La case 0 est liée à toutes les cases de sa ligne car, sur une même ligne, il ne peut pas y avoir deux fois le même chiffre.
Cette case est aussi liée à toutes les cases de sa colonne et à toutes celles de sa région.

Afin d’éviter toutes confusions entre les numéros de cases (de 0 à 15) et les valeurs de celles-ci (entre 1 et 4), nous allons raisonner avec des couleurs : {1 : 'bleu', 2 : 'vert', 3 : 'rouge', 4 : 'jaune'}.
Ainsi, la première grille : Grille n°1

devient Grille n°1

  1. Quel sera le degré de chaque sommet ?

    Une réponse

    Chaque sommet est lié à trois autres sur sa ligne, à trois autres sur sa colonne et à un dernier non encore sélectionné dans sa région, soit 7 arêtes par sommet.
    Chaque sommet est donc de degré 7.

  2. Recopiez et complétez le graphe ci-dessous en ajoutant les arêtes pour chaque sommet. Graphe n°1

  3. Coloriez les sommets dont on connait la couleur.

  4. Ajoutez, à côté de chaque sommet qui n’a pas de couleur, le nombre de sommets de couleurs différentes avec lesquels il est en relation.

    Une réponse

    Graphe n°2

  5. A votre avis, par quel sommet peut-on commencer le remplissage ?

    Une réponse

    N'importe lequel convient ici.

  6. Téléchargez le fichier graphe-sudoku.ggb.
    En utilisant ce fichier, essayez de résoudre la grille n°2 de la même manière : Grille n°2

    Une réponse

    On ajoute, à côté de chaque sommet qui n’a pas de couleur, le nombre de sommets de couleurs différentes avec lesquels il est en relation : Graphe n°3

    On commence par le sommet n°3, pour lequel ce nombre est le plus grand : Graphe n°3

    On termine : Graphe n°3