Sudoku en terminal

C'est un petit projet que j'ai fait à l'époque où j'apprenais le C, et je voulais quelque chose de concret pour pratiquer les algorithmes, la gestion des entrées utilisateur et une structure de programme “réaliste”.
C'est un Sudoku jouable dans le terminal : tu peux soit saisir une grille à la main, soit en générer une aléatoirement, puis la résoudre toi-même ou laisser le programme le faire.
Le code est disponible sur GitHub.

Ce que ça fait

Le programme couvre quelques usages simples : générer une grille, jouer manuellement en entrant des coordonnées, et (optionnellement) demander au solveur de terminer la grille.
J'ai aussi passé un peu de temps sur l'affichage pour que la grille soit lisible, avec des coordonnées lignes/colonnes, en utilisant des caractères Unicode de tracé de boîtes.

Fonctionnalités principales

Génération aléatoire de grilles.
Résolution manuelle via saisie des coordonnées x/y et d'un chiffre.
Solveur automatique (backtracking).
Validation des coups : pas de doublon sur une ligne, une colonne ou un bloc (3 x 3), et uniquement le remplissage de cases vides.

Comment fonctionne le solveur

Le solveur automatique utilise le backtracking : il remplit la grille étape par étape, et dès qu'il arrive à une contradiction il “revient en arrière” pour essayer une autre option.
Concrètement, il répète la même boucle : choisir une case vide, tester les chiffres de 1 à 9 qui respectent les règles (ligne, colonne, bloc (3 x 3)), puis appeler récursivement la résolution jusqu'à compléter la grille.

Pour l'accélérer (et parce que je voulais expérimenter), le solveur ne prend pas simplement la première case vide : il cherche d'abord la case vide avec le plus petit nombre de candidats possibles.
Ça réduit les branches inutiles et, en général, ça accélère la résolution, parce que l'algorithme attaque les cases “les plus difficiles” plus tôt.

L'algorithme

Chercher une case vide (un 0 dans ma grille).
S'il n'y a plus de cases vides, le Sudoku est résolu.
Pour la case vide choisie, calculer quels chiffres de 1 à 9 sont autorisés :
- Pas déjà présents sur la même ligne.
- Pas déjà présents sur la même colonne.
- Pas déjà présents dans le même bloc (3 x 3).
Essayer chaque chiffre autorisé :
- Le placer dans la case.
- Résoudre récursivement le reste de la grille.
- En cas d'échec plus tard, remettre la case à 0 et tenter le chiffre suivant.
Si aucun chiffre ne marche, retour arrière jusqu'à la décision précédente.

Mini pseudo-code

resoudre(grille):
  case = trouver_case_vide(grille)
  si case est nulle:
    retourner Vrai  // Sudoku résolu

  candidats = calculer_chiffres_autorises(grille, case)

  pour chaque chiffre dans candidats:
    placer chiffre dans case
    si résoudre(grille) est Vrai:
      retourner Vrai
    remettre case à 0  // retour arrière

  retourner Faux  // aucun chiffre ne marche

Génération aléatoire de grilles

Le mode “grille aléatoire” commence par placer un petit nombre de valeurs aléatoires valides, puis utilise le solveur pour compléter la grille jusqu'à une solution complète.
Ensuite, il retire un certain nombre de cases (en les remettant à 0) pour créer une grille jouable.

Concrètement, le code :

Initialise l'aléatoire avec srand(time(NULL)).
Place 10 chiffres valides au hasard.
Résout entièrement la grille.
Retire 55 cases remplies.

C'est juste un simple projet d'apprentissage, donc le générateur ne garantit pas une solution unique à chaque fois.

Ce que j'ai appris (et limites)

Ce projet m'a appris pas mal de bases : récursivité, backtracking, et comment structurer de petits programmes C avec des fonctions claires et une validation d'entrée soignée.

Limites / améliorations possibles

Le générateur peut produire des grilles qui n'ont pas une solution unique (OK pour une démo d'apprentissage, moins bien pour un “vrai” générateur de Sudoku).
Si je le refaisais, je séparerais plus proprement l'UI de la logique du solveur (plusieurs fichiers, gestion d'état plus claire).
Il n'y a pas de réglage de niveau de difficulté pour les grilles générées, ce qui pourrait être une amélioration intéressante.

Jeu de Sudoku en terminal (C)