Soit une grille de 9×9 cases. La grille est notamment subdiviser en 9 zones (dans l'exemple, entourées en gros traits). Quelques cases de la grille sont déjà remplies par un chiffre.

On souhaite compléter les cases de la grille en choisissant des chiffres entre 1 et 9 (compris) La solution doit respecter les contraintes :

• dans chaque colonne, chaque chiffre présent 1x,
• dans chaque ligne, chaque chiffre présent 1x,
• dans chaque zone, chaque chiffre présent 1x.

Tenant compte des chiffres déjà écrits dans la grille, il existe une et une seule solution.

Les méthodes de résolution sont nombreuses et certaines sont très élaborées. Pour s'en convaincre, voici un guide.

Nous allons nous contenter de méthodes simples.

Dans une case, il ne peut y avoir qu'un chiffre de 1 à 9. Mais s'il y a déjà un 9 dans la même ligne et un 8 dans la même colonne, on sait que 8 et 9 sont exclus. En faisant ce genre de tri on peut trouver trier les options restantes pour chaque case. En jargon de sudoku, on appelle ces possibilités des candidats.

On comprend par exemple ici que dans la 1e ligne 2e colonne, la présence des chiffres 13678 dans la 2e colonne, 23 dans la 1e ligne et 3578 dans la zone font que seuls 4 et 9 restent possibles.

Première technique, la plus simple, chercher les cases dans lesquelles un seul candidat est possible.

Exemple, dans la première case, seul le 1 est possible. On peut donc écrire 1 dans cette case. Tenant compte de choix, on peut mettre à jour les candidats dans les cases concernées.

On peut continuer tant que l'on trouve des cases pour lesquelles il y a un candidat unique.

Pour cette grille facile, cette technique suffit.

Dans la 7e colonne, le 3 n'a qu'une place possible.

On peut donc écrire le 3 dans cette case.

D'autres techniques sont plus élaborées. Je n'en cite qu'une pour l'exemple.

En 2e colonne, les 2 premières cases ne peuvent contenir que 4 et 9. Cela signifie que le 4 et le 9 ne peuvent pas être ailleurs ce qui exclu le 9 dans la 7e case de la colonne.

C'est seulement un exemple. C'est une technique banale mais elle est difficile à programmer.

Nous avons évoqué des techniques qui correspondent aux techniques qu'utiliserait un humain pour résoudre une grille. La machine ayant une grande puissance de calcul, le plus simple pour elle n'est pas nécessairement de faire comme l'humain.

La technique la plus efficace pour la machine et qui vient à bout de n'importe quelle grille quelle que soit sa difficulté est la technique de force brute consistant à tout essayer.

Soyons plus clair : Vraiment tout essayer peut être long, pour la machine. On peut se contenter de

1. trier les candidats,
2. chercher les cases où un seul candidat est possible,
3. si on arrive dans un cas où toute case vide a plus d'un candidat, choisir une case vide (la première ou même au hasard) puis choisir un candidat possible (le premier ou même au hasard) et poursuivre. On note bien que l'on a fait un choix de candidat.
4. si on aboutit à une contradiction (une case dans laquelle plus aucun candidat n'est possible) on remonte au dernier choix de candidat et on rejette ce candidat.

On finit par aboutir à une solution qui est forcément la bonne puisqu'il n'y en a qu'une.

Pour mettre en œuvre un outil de résolution automatique nous aurons besoin de

1. optionnel : lire une grille stockée dans un fichier texte
2. stocker la grille dans la mémoire,
3. d'afficher le contenu de la grille sous une forme assez lisible,
4. de lire et écrire dans la grille,
5. de déterminer, en fonction de l'état de la grille, les candidats possibles dans une case donnée.
6. optionnel : écrire une grille dans un fichier texte

Ces méthodes suffisent pour une résolution simple. La résolution consiste à parcourir la grille à la recherche des cases vides, chercher les candidats possibles pour cette case et quand il n'y en a qu'un, modifier la grille en écrivant ce candidat dans la case, poursuivre ainsi tant qu'on trouve de nouvelles valeurs à écrire.

Si vous voulez un outil plus puissant, vous pouvez essayer d'implémenter la force brute.

Prenons la grille exemple. On peut adopter deux approches qui ont leurs qualités et leurs défauts.

# grille, tableau 2D
grille = [ [0, 0, 0, 0, 3, 0, 2, 0, 0],
           [7, 0, 5, 2, 0, 0, 0, 9, 0],
           [8, 3, 0, 4, 6, 9, 1, 5, 0],
           [2, 0, 0, 0, 9, 4, 0, 3, 0],
           [9, 8, 0, 0, 0, 3, 0, 0, 2],
           [6, 1, 3, 8, 0, 2, 0, 0, 9],
           [4, 0, 0, 1, 0, 0, 7, 0, 3],
           [3, 7, 8, 0, 2, 0, 4, 0, 0],
           [0, 6, 1, 0, 0, 0, 0, 0, 0] ]
# lecture de la ligne 3 colonne 2
grille[3][2]
# le coin supérieur gauche est en ligne 0 colonne 0

# grille ramenée à une simple ligne
grille = [0, 0, 0, 0, 3, 0, 2, 0, 0,
          7, 0, 5, 2, 0, 0, 0, 9, 0,
          8, 3, 0, 4, 6, 9, 1, 5, 0,
          2, 0, 0, 0, 9, 4, 0, 3, 0,
          9, 8, 0, 0, 0, 3, 0, 0, 2,
          6, 1, 3, 8, 0, 2, 0, 0, 9,
          4, 0, 0, 1, 0, 0, 7, 0, 3,
          3, 7, 8, 0, 2, 0, 4, 0, 0,
          0, 6, 1, 0, 0, 0, 0, 0, 0]

# lecture de la ligne 3 colonne 2
grille[3*9+2]
# le coin supérieur gauche est en ligne 0 colonne 0

La grille à 1 dimension me parait meilleure. Dans tous les cas, il est préférable de ne pas manipuler la grille directement. Mieux vaut créer les fonctions read_cell et set_cell qui prennent charge la lecture et l'écriture dans une case du tableau.